Running Sum of an Array
Bir tamsayı dizisi nums veriliyor. Uzunluğu aynı olan yeni bir dizi döndürün; bu dizinin i indeksindeki elemanı, soldan ilk i+1 sayıyı okuduktan sonraki toplam olan nums[0] + nums[1] + ... + nums[i] değeridir.
Fonksiyon
- numsinteger-array
- soldan sağa toplanacak sayılar
- Döndürürinteger-array
- nums içindeki her öğe için birer tane olmak üzere çalışan toplamlar
Kısıtlar
1 ≤ nums.length ≤ 5000-104 ≤ nums[i] ≤ 104- Her birikimli toplam 32 bitlik işaretli bir tamsayıya sığar.
Örnekler
- Girdi
- nums = [3, 1, 4, 1, 5]
- Çıktı
- [3, 4, 8, 9, 14]
- Açıklama
- Toplamaya devam et:
3, sonra3 + 1 = 4,4 + 4 = 8,8 + 1 = 9ve9 + 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ından3 + (-3) = 0.
- Girdi
- nums = [7]
- Çıktı
- [7]
- Açıklama
- Tek bir sayının tek bir toplamı vardır; bu da sayının kendisidir, dolayısıyla cevap
[7].
Gönderirken +13 gizli test
Ek soru
Her hücrenin sol üst köşeden o hücreye kadar olan dikdörtgenin toplamını tuttuğu bir ızgara için de aynısını oluşturabilir misin?
İpuçları
Tek tek açın. Her biri biraz daha fazlasını gösterir.
iindeksindeki yanıt,i-1indeksindeki yanıtla nasıl ilişkilidir?İki toplam tam olarak bir sayı,
nums[i]kadar farklıdır. Baştan başlayarak bir öneki yeniden toplamanız gerekmez.totaladında tek bir değişken tut.numsdizisini soldan sağa doğru dolaş, her sayıyıtotaldeğişkenine ekle vetotaldeğerini yanıtta aynı indekse yaz.
Çözüm
Her yanıt, nums dizisinin bir önek toplamıdır ve komşu iki önek yalnızca bir eleman bakımından farklıdır. Her öneki baştan yeniden hesaplamak işin neredeyse tamamını tekrarlar; bir toplamı ileriye taşımaksa her yanıtı tek bir toplamayla elde etmenizi sağlar. Sonuç, hızlı aralık toplamlarının temelindeki araç olan önek toplamı dizisidir.
Sıfırdan başlayarak her öneki topla
Sezgi
Tanımı kelimesi kelimesine uygulayın. Her i indeksi için 0'dan başlayan yeni bir toplam oluşturun, nums[0] ile nums[i] arasındaki değerleri toplayın ve sonucu kaydedin. [3, 1, 4, 1, 5] için son yanıt beş sayının tümünü toplar: 3 + 1 + 4 + 1 + 5 = 14.
Bu doğrudur, ama aynı işlemi tekrarlar. 4. indeks için toplam, nums[0] değerinden yeniden başlar; oysa 3. indeks için toplam olan 9, ilk dört sayının toplamını zaten içerir. i indeksi için i+1 toplama gerekir; dolayısıyla tüm dizi için gereken işlem sayısı 1 + 2 + ... + n = n(n+1)/2 olur. n = 5000 için bu, 5000 toplama yeterliyken yaklaşık 1.25 × 10^7 toplama demektir.
Zaten döndüreceğiniz yanıt dizisinin dışında yalnızca bir toplam ve iki indeks tutar; bu nedenle ek alan O(1)'dir.
Algoritma
nuzunluğunda bir yanıt dizisi oluştur.- Her
iindeksi içintotal = 0ayarla. 0ileiarasındaki herjiçinnums[j]değerinitotaldeğerine ekle.totaldeğerini yanıtıniindeksinde sakla ve son indeksten sonra yanıtı döndür.
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 resultBiriken toplamı 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]. Yani bir adımdan daha geriye bakmana hiç gerek yok. Tek bir total değişkeni tut, okuduğun her sayıyı buna ekle ve yeni değeri yanıta yaz.
[3, 1, 4, 1, 5] için total sırasıyla 3, 4, 8, 9, 14 olur ve bu beş değer yanıtı oluşturur. Her eleman bir kez okunur ve bir toplama işlemi gerektirir; bu nedenle zaman karmaşıklığı O(n) olur. Yanıt dizisi dışında kullanılan tek bellek total olduğundan, ek alan karmaşıklığı O(1) olur.
Buradaki hiçbir toplam 5000 × 10^4 = 5 × 10^7 değerini aşamaz; bu da 32 bitlik bir tamsayıya sığar. Daha büyük girdilerde önek toplamları taşma açısından klasik bir risk oluşturur ve 64 bitlik bir toplam kullanmak güvenli varsayılandır.
Algoritma
nuzunluğunda bir cevap dizisi oluştur vetotal = 0olarak ayarla.- Soldan sağa indeksler boyunca ilerle ve
nums[i]değerinitotaldeğerine ekle. totaldeğerini cevabıniindeksine 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üde gerçek işi yapan tek bir satır var; bu nedenle hatalar, toplamın nerede tutulduğu ve nereye gittiğiyle ilgilidir.
totaldeğişkenini döngünün içinde sıfırlamak. Her yanıt tek başınanums[i]olur ve[3, 1, 4]değişmeden geri döner.i = 0durumunu ele almadanresult[i] = result[i-1] + nums[i]kullanmak. Çoğu dilde-1indeksi sınırların dışındadır; Python'da ise son elemandır. Bu nedenle 0'dan başlayan, yerinde çalışan bir sürüm ilk sayıya son sayıyı ekler.- İlk yaklaşımın iç döngüsünü
j < ikoşulunda durdurmak. Böylecenums[i]dışarıda kalır ve her yanıt bir sayı eksik olur. - Yanıtı kopyalayarak büyütmek. R'de
result <- c(result, total)her adımda vektörün tamamını kopyalar ve hızlı yaklaşımı yeniden karesel hale getirir. Önce uzunluğun tamamı için bellek ayırın. - C'de
*returnSize = numsSizeyazmayı unutmak. Bu olmadan çağıran taraf kaç toplamı okuyacağını bilemez.
Sıkça sorulan sorular4
Dizinin birikimli toplamı nedir?
Bu, her bir öğesi ilk dizideki aynı konuma kadar olan ve o konum dâhil tüm öğelerin toplamı olan ikinci bir dizidir. Önek toplamı veya kümülatif toplam olarak da adlandırılır. [3, 1, 4, 1, 5] dizisinin kümülatif toplamı [3, 4, 8, 9, 14] şeklindedir.
Çalışan toplamı hesaplamanın zaman karmaşıklığı nedir?
Soldan sağa taşınan tek bir toplamla, her öğe için bir toplama işlemi yapılır; zaman karmaşıklığı O(n), yanıta ek olarak kullanılan alan ise O(1)'dir. Her öneki baştan yeniden hesaplamak n(n+1)/2 toplama işlemi gerektirir; bu da O(n²)'dir.
Çalışan toplamı yerinde hesaplayabilir misin?
Evet. 1. indeksten sona kadar ilerleyin ve nums[i] += nums[i-1] işlemini yapın. Böylece her eleman kendi önek toplamını tutar; çünkü nums[i-1] zaten kendisinden önceki her şeyin toplamına dönüştürülmüştür. Bu yöntem girdi dışında başka bir dizi kullanmaz, ancak özgün değerleri yok eder.
Önek toplamları aralık toplamı sorgularına nasıl yardımcı olur?
Biriken toplamları elde ettikten sonra, herhangi bir nums[l..r] diliminin toplamı prefix[r] - prefix[l-1] olur; l = 0 olduğunda ise prefix[r] olur. [3, 4, 8, 9, 14] biriken toplamlarıyla, 2'den 4'e kadar olan indekslerin toplamı 14 - 4 = 10 olur. Tek bir O(n) geçişten sonra her sorgu O(1) zamanda yanıtlanır.
Benzer problemler
Aynı fikirleri kullanan problemler. İki üçünü çözmek bir kalıbı kalıcı hale getirir.
Python
def runningSum(nums):
# Kodu buraya yazınDurum 1
Durum 2
Durum 3
Girdi
nums = [3, 1, 4, 1, 5]
Beklenen
[3, 4, 8, 9, 14]