Running Sum of an Array

Q: Dizinin çalışan toplamı nedir?

Bu, her öğesi birincideki aynı konuma kadar olan her şeyin toplamını içeren ikinci bir dizidir. Buna önek toplamı veya kümülatif toplam da denir. [3, 1, 4, 1, 5] dizisinin kümülatif toplamı [3, 4, 8, 9, 14] şeklindedir.

Q: Birikimli toplamı hesaplamanın zaman karmaşıklığı nedir?

Soldan sağa taşınan tek bir toplamla O(n) zaman ve yanıt dışında O(1) ek alan. Her öneki baştan yeniden hesaplamak O(n²) zaman alır.

Q: Çalışan toplamı yerinde hesaplayabilir misin?

Evet. 1. indexten sona kadar ilerleyin ve nums[i] += nums[i-1] ifadesini ayarlayın. O noktada nums[i-1] zaten kendisine kadar olan her şeyin toplamını içerir, böylece her eleman ön ek toplamıyla sonuçlanır. Orijinal değerleri kaybedersiniz.

Q: Önek toplamları aralık toplamı sorgularına nasıl yardımcı olur?

Bir dilimin nums[l..r] toplamı prefix[r] - prefix[l-1] olur; l = 0 olduğunda ise prefix[r] olur. [3, 4, 8, 9, 14] dizisinde 2 ile 4 arasındaki indekslerin toplamı 14 - 4 = 10 eder. Tek bir O(n) geçişinden sonra her sorgu O(1) zaman alır.

BaşlangıçÖnek toplamı

+10

Bir tam sayılar dizisi nums alırsın. Uzunluğu aynı olan ve i indeksindeki elemanı, ilk i+1 sayının toplamı olan nums[0] + nums[1] + ... + nums[i] değerine eşit olan yeni bir dizi döndür.

Fonksiyon

runningSum(nums: integer-array) → integer-array

numsinteger-array: soldan sağa toplanacak sayılar
Döndürürinteger-array: nums içindeki her öğe için bir tane olmak üzere çalışan toplamlar

Kısıtlar

1 ≤ nums.length ≤ 5000
-10⁴ ≤ nums[i] ≤ 10⁴
Çalışan her toplam 32 bitlik işaretli bir tam sayıya sığar.

Örnekler

Girdi: nums = [3, 1, 4, 1, 5]
Çıktı: [3, 4, 8, 9, 14]
Açıklama: Eklemeye devam et: 3, ardından 3 + 1 = 4, 4 + 4 = 8, 8 + 1 = 9 ve 9 + 5 = 14. Her toplam, en son eklenen sayının indeksine gider.

Girdi: nums = [-2, 5, -3]
Çıktı: [-2, 3, 0]
Açıklama: Negatif sayılar toplamı düşürür: -2, ardından -2 + 5 = 3, ardından 3 + (-3) = 0.

Girdi: nums = [7]
Çıktı: [7]
Açıklama: Tek bir sayının, kendisinden oluşan tek bir toplamı vardır; dolayısıyla cevap [7].

Ek soru

Bir ızgara için de aynı şeyi oluşturabilir misin; her hücre, sol üst köşeden o hücreye kadar olan dikdörtgenin toplamını tutsun?

İpuçları

Tek tek açın. Her biri biraz daha fazlasını gösterir.

3 ipucundan 0 açıldı

Çözüm

Her yanıt, nums dizisinin bir önekinin toplamıdır ve yan yana gelen önekler tek bir eleman bakımından farklıdır. Her öneki baştan yeniden hesaplamak, işin neredeyse tamamını tekrarlar. Bunun yerine toplamı ileriye taşı; böylece her yanıt için tek bir toplama işlemi yeterli olur.

Sıfırdan başlayarak her öneki topla

Sezgi

Tanımı izleyin: her i indeksi için toplamı 0'dan başlatın, nums[0] ile nums[i] arasındaki değerleri ekleyin ve sonucu kaydedin. Her yanıt tanımlandığı şekilde tam olarak hesaplandığı için bu doğrudur.

i indeksi i+1 toplama gerektirir; bu nedenle dizi için gereken işlem sayısı n(n+1)/2 olur: n = 5000 için yaklaşık 1.25 × 10^7 toplama gerekir; 5000 yeterli olur.

Algoritma

n uzunluğunda bir cevap dizisi oluşturun.
Her i indeksi için total = 0 olarak ayarlayın.
0 ile i arasındaki her j için nums[j] değerini total değerine ekleyin.
total değerini cevap dizisinin i indeksinde saklayın ve son indeksten sonra cevabı döndürün.

def runningSum(nums):
    result = []
    for i in range(len(nums)):
        total = 0
        for j in range(i + 1):
            total += nums[j]
        result.append(total)
    return result

Toplamı sürekli güncel tut

Sezgi

İlk i+1 sayının toplamı, ilk i sayının toplamı ile nums[i] değerinin toplamıdır: result[i] = result[i-1] + nums[i]. Bu yüzden bir adımdan daha geriye bakmana hiç gerek yoktur ve total adlı tek bir değişken yeterlidir. [3, 1, 4, 1, 5] için sonuç 3, 4, 8, 9, 14 olur; cevap da budur.

Her öğe için bir toplama işlemi gerekir: O(n) zaman ve cevap dışında O(1) ek alan.

Algoritma

n uzunluğunda bir cevap dizisi oluştur ve total = 0 olarak ayarla.
İndeksler arasında soldan sağa ilerle ve nums[i] değerini total değerine ekle.
total değerini cevabın i indeksine yaz.
Cevabı döndür.

def runningSum(nums):
    result = []
    total = 0
    for num in nums:
        total += num
        result.append(total)
    return result

Tuzaklar ve uç durumlar

Döngünün içinde total değerini sıfırlamak. Her yanıt yalnızca nums[i] olur ve [3, 1, 4] değişmeden geri döner.
i = 0 iken result[i-1] değerini okumak. Çoğu dil dizinin sınırları dışına çıkar; Python son öğeyi okur, bu nedenle yerinde yapılan bir sürüm son sayıyı ilk sayıya ekler.
Kaba kuvvet yaklaşımının iç döngüsünü j < i koşulunda durdurmak. Bu, nums[i] değerini dışarıda bırakır; dolayısıyla her yanıt bir sayı eksik olur.
R'de, result <- c(result, total) ile yanıtı büyütmek vektörün her adımda kopyalanmasına neden olur ve hızlı yaklaşımı karesel zamana çıkarır. Önce tam uzunluğu ayırın.
C'de *returnSize = numsSize atamasını unutmak. Böylece çağıran taraf kaç toplamı okuyacağını bilemez.

Sıkça sorulan sorular4

Dizinin çalışan toplamı nedir?

Bu, her öğesi birincideki aynı konuma kadar olan her şeyin toplamını içeren ikinci bir dizidir. Buna önek toplamı veya kümülatif toplam da denir. [3, 1, 4, 1, 5] dizisinin kümülatif toplamı [3, 4, 8, 9, 14] şeklindedir.

Birikimli toplamı hesaplamanın zaman karmaşıklığı nedir?

Soldan sağa taşınan tek bir toplamla O(n) zaman ve yanıt dışında O(1) ek alan. Her öneki baştan yeniden hesaplamak O(n²) zaman alır.

Çalışan toplamı yerinde hesaplayabilir misin?

Evet. 1. indexten sona kadar ilerleyin ve nums[i] += nums[i-1] ifadesini ayarlayın. O noktada nums[i-1] zaten kendisine kadar olan her şeyin toplamını içerir, böylece her eleman ön ek toplamıyla sonuçlanır. Orijinal değerleri kaybedersiniz.

Önek toplamları aralık toplamı sorgularına nasıl yardımcı olur?

Bir dilimin nums[l..r] toplamı prefix[r] - prefix[l-1] olur; l = 0 olduğunda ise prefix[r] olur. [3, 4, 8, 9, 14] dizisinde 2 ile 4 arasındaki indekslerin toplamı 14 - 4 = 10 eder. Tek bir O(n) geçişinden sonra her sorgu O(1) zaman alır.

def runningSum(nums):
    # Kodu buraya yazın

Test #1

Test #2

Test #3

Argüman

nums = [3, 1, 4, 1, 5]

Beklenen Çıktı

[3, 4, 8, 9, 14]