Subarray Sum Equals K

+10

Bir tamsayı dizisi nums ve bir tamsayı k veriliyor. Elemanlarının toplamı tam olarak k olan alt dizilerin sayısını bulun. Alt dizi, yan yana bulunan bir veya daha fazla elemandan oluşan bir dizidir. Aynı değerleri içerseler bile, farklı konumlarda başlayıp biten alt diziler ayrı ayrı sayılır. Değerler negatif veya sıfır olabilir.

Fonksiyon

subarraySum(nums: integer-array, k: integer) → integer

numsinteger-array: negatif değerler ve sıfırlar içerebilen tamsayı dizisi
kinteger: Sayılabilmesi için bir alt dizinin ulaşması gereken toplam
Döndürürinteger: Elemanlarının toplamı k olan alt dizilerin sayısı

Kısıtlar

1 ≤ nums.length ≤ 2 × 10⁴
-1000 ≤ nums[i] ≤ 1000
-10⁷ ≤ k ≤ 10⁷
Bu uzunluktaki bir dizinin en fazla 200,010,000 alt dizisi vardır; dolayısıyla yanıt 32 bitlik işaretli bir tam sayıya sığar.

Örnekler

Girdi: nums = [3, 4, -7, 1, 3, 3, 1, -4]k = 7
Çıktı: 4
Açıklama: Dört dizi toplamda 7 eder: [3, 4], [1, 3, 3], [3, 3, 1] ve [3, 4, -7, 1, 3, 3]. Son dizide -7, 3 ile 4’ü götürür ve toplam daha sonra yeniden 7’ye yükselir; dolayısıyla toplamı k değerini geçtikten sonra bile bir dizi eşleşebilir.

Girdi: nums = [1, -1, 0]k = 0
Çıktı: 3
Açıklama: Üç alt dizinin toplamı 0 eder: [1, -1], [0] ve dizinin tamamı [1, -1, 0]. [-1, 0] dizisinin toplamı -1 eder, bu yüzden sayılmaz.

Girdi: nums = [2, 2, 2]k = 4
Çıktı: 2
Açıklama: 0 ve 1 indekslerindeki [2, 2] dizisi ile 1 ve 2 indekslerindeki [2, 2] dizisi aynı değerlere sahiptir ancak farklı konumlarda yer alır, bu nedenle ikisi de sayılır. Dizinin toplamı 6'dır.

Gönderirken +17 gizli test

Ek soru

Çözümü, yine O(n) zamanda, toplamı k olan en uzun alt dizinin uzunluğunu döndürecek şekilde nasıl değiştirirdin?

İpuçları

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

3 ipucundan 0 açıldı

Çözüm

n sayıdan oluşan bir dizinin n(n+1)/2 alt dizisi vardır; n = 2 × 10^4 olduğunda bu sayı yaklaşık 2 × 10^8 olur, bu yüzden her birinin toplamını hesaplamak çok yavaştır. Negatif değerler kayan pencere yöntemini de devre dışı bırakır: Bir pencerenin toplamı düşüp sonra yeniden yükselebilir, dolayısıyla pencereyi ne zaman daraltacağınızı belirleyen bir kural yoktur. Problemi çözen fikir, her alt dizi toplamını iki önek toplamının farkı olarak yazmaktır. O hâlde geçerli elemanda biten ve toplamı k olan alt dizileri saymak, daha önceki önek toplamları arasından geçerli önek toplamından k çıkarıldığında elde edilen değere eşit olanları saymak anlamına gelir; bir karma tablo bunu tek geçişte yanıtlar.

Her başlangıçta çalışan bir toplam

Doğru, ama en büyük testlerde bitmiyor

Sezgi

Her alt dizinin bir ilk indeksi start ve bir son indeksi end vardır. Her çifti ziyaret edip toplamını kontrol edersen her alt diziyle tam olarak bir kez karşılaşırsın; böylece sayım doğru olur.

Her alt dizinin toplamını bulmak için üçüncü bir döngüye ihtiyacın yok. start değerini sabitle, ardından end değerini her seferinde bir adım sağa ilerlet ve nums[end] değerini biriken total değerine ekle. Toplam, start ile end arasındaki elemanların toplamını her zaman tutar; dolayısıyla her alt dizi bir toplama ve bir karşılaştırma gerektirir.

Toplam k değerine ulaştığında veya onu geçtiğinde durma. Daha sonraki negatif bir değer toplamı yeniden düşürebilir: ilk örnekte, 0 indeksinden başlayan toplam 3, 7, 0, 1, 4, 7 şeklinde ilerler; yani bu başlangıç için 5 indeksinde ikinci bir eşleşme vardır.

Maliyet, çiftlerin sayısıdır. n = 2 × 10^4 olduğunda yaklaşık 2 × 10^8 çift vardır; bu C için uygundur, ancak Python, Ruby veya R için çok yavaştır.

Algoritma

count'u 0 olarak ayarla.
0'dan n-1'e kadar her start için total'ı 0 olarak ayarla.
start'ten n-1'e kadar her end için nums[end]'i total'a ekle.
total değeri k'ye eşitse count'a 1 ekle ve her iki durumda da devam et.
count'u döndür.

def subarraySum(nums, k):
    n = len(nums)
    count = 0
    for start in range(n):
        total = 0
        # Grow the subarray that begins at start, one element at a time
        for end in range(start, n):
            total += nums[end]
            if total == k:
                count += 1
    return count

Sayım haritasıyla önek toplamları

Sezgi

prefix[j], ilk j elemanın toplamı olsun; boş önek için prefix[0] = 0 olsun. i indeksinden j-1 indeksine kadar olan alt dizi toplamı prefix[j] - prefix[i] olur. Dolayısıyla mevcut elemanda biten bir alt dizinin toplamı, önceki bir önek toplamı mevcut önek toplamı eksi k değerine eşit olduğunda tam olarak k olur. Bu tür önceki öneklerin her biri, eşleşen bir alt dizinin başlangıç noktasını belirtir.

Diziyi bir kez dolaş. Biriken önek toplamını ve her önek toplamının kaç kez görüldüğünü tutan seen adlı bir hash map kullan. Her elemanda önce seen[prefix - k] değerini sayaca ekle, ardından mevcut öneki kaydet. Kaydetmeden önce arama yapmak, alt dizinin boş olmasını engeller: k = 0 olduğunda önce kaydetmek, mevcut önekin kendisiyle eşleşmesine yol açardı.

k = 7 olan ilk örneği ele alalım. Önek toplamları 0, 3, 7, 0, 1, 4, 7, 8, 4 şeklindedir. Önek, 1. indeksten sonra 7'ye ulaştığında haritada bir 0 bulunur; bu da [3, 4] alt dizisini verir. 5. indeksten sonra tekrar 7'ye ulaştığında haritada iki 0 bulunur; boş önek ve -7'den sonraki önek. Bunlar sırasıyla [3, 4, -7, 1, 3, 3] ve [1, 3, 3] alt dizilerini verir. 6. indeksten sonra toplam 8 olduğunda haritada bir 1 bulunur; bu da [3, 3, 1] alt dizisini verir. Böylece toplam 4 olur.

Haritayı başlangıçta bir kez görülmüş 0 ile doldurmak, 0. indekste başlayan alt dizilerin sayılmasını sağlar. Küme yerine sayım haritası kullanmak önemlidir; çünkü aynı önek toplamı tekrarlanabilir ve her tekrar farklı bir alt diziyi başlatır. Her eleman için bir arama ve bir güncelleme yapılır; dolayısıyla zaman karmaşıklığı O(n), harita ise en fazla n+1 anahtar tutar.

Algoritma

seen eşlemesini seen[0] = 1 ile oluşturun ve prefix ile count değerlerini 0 olarak ayarlayın.
Her bir öğeyi prefix değerine ekleyin.
Eksik bir anahtarı 0 kabul ederek seen[prefix - k] değerini count değerine ekleyin.
seen[prefix] değerini 1 artırın.
count değerini döndürün.

def subarraySum(nums, k):
    # seen[p] = how many prefixes so far add up to p; the empty prefix adds up to 0
    seen = {0: 1}
    prefix = 0
    count = 0
    for num in nums:
        prefix += num
        # Each earlier prefix equal to prefix - k starts a subarray that ends here and sums to k
        count += seen.get(prefix - k, 0)
        seen[prefix] = seen.get(prefix, 0) + 1
    return count

Tuzaklar ve uç durumlar

Yanlış yanıtların çoğu, girdideki her değerin pozitif olduğunu varsaymaktan ya da iki eşleme işleminin sırasını karıştırmaktan kaynaklanır.

Toplam k değerini aşınca daralan kayan pencere, negatif değerlerde başarısız olur. İlk örnekte 4 yerine 2 döndürür: toplam 6. indiste 7'yi aşana kadar pencerenin sol kenarı 0. indiste kalır; bu nedenle [1, 3, 3] veya [3, 3, 1] alt dizilerini hiçbir zaman denemez.
seen[0] = 1 satırını eklememek, 0. indiste başlayan tüm alt dizileri gözden kaçırır. nums = [5] ve k = 5 için 1 yerine 0 döndürür.
Arama yapmadan önce mevcut önek toplamını kaydetmek, k değeri 0 olduğunda boş alt dizileri sayar. [1, -1, 0] için 3 yerine 6 döndürür.
Sayı sayma eşlemesi yerine önek toplamları kümesi kullanmak, tekrarları eksik sayar. [0, 0, 0] ve k = 0 için yanıt 6'dır; çünkü aynı önek toplamının önceki her kopyası farklı bir alt dizi başlatır.
Kaba kuvvet yönteminde, toplam k değerini aşınca iç döngüden çıkmak, kayan pencereyle aynı nedenle yanlıştır.

Sıkça sorulan sorular4

Subarray Sum Equals K'nin zaman karmaşıklığı nedir?

Önek toplamı ve hash map çözümü O(n) zamanda ve O(n) ek alanda çalışır: tek geçişte, her eleman için bir arama ve bir güncelleme yapılır. Çalışan toplamla her alt diziyi kontrol etmek O(n²) zaman alır; her alt dizinin toplamını baştan hesaplamak ise O(n³) zaman alır.

Subarray Sum Equals K için kayan pencere neden işe yaramaz?

Kayan pencere, pencere büyüdüğünde toplamın artmasına ve küçüldüğünde azalmasına dayanır; bu yalnızca her değer pozitif olduğunda geçerlidir. Negatif değerler varsa, toplamı zaten çok büyük olan bir pencere daha da büyüdükten sonra eşleşmeye dönüşebilir; bu nedenle sol kenarı ne zaman ilerleteceğinizi belirleyen bir kural yoktur. Her değer pozitif olsaydı, kayan pencere bunu O(n) zamanda ve O(1) alanda çözebilirdi.

Hash map neden 0'ı 1 ile eşleştirerek başlar?

Bu girdi, toplamı 0 olan ilk öğeden önceki boş öneki temsil eder. İndeks 0'dan başlayan bir alt dizi, geçerli önek toplamından bu boş önek çıkarıldığında elde edilen toplamı verir; bu nedenle girdi olmadan bu alt diziler hiçbir zaman sayılmaz. nums = [5] ve k = 5 için 5 - 5 = 0 araması bu girdiyi bulur ve 1 döndürür.

Alt dizi toplamı K'ya eşit olacak şekilde O(1) ek alan kullanarak çözülebilir mi?

Tek geçişli yöntemle olmaz. Bir öğede biten eşleşmeleri saymak için, ondan önce hangi önek toplamlarının geldiğini bilmen gerekir ve birbirinden farklı en fazla n+1 tane olabilir. Eşleme olmadan O(n²) çalışma süresine sahip toplamı hesaplama yöntemine geri dönersin. Tüm değerler pozitif olduğunda, kayan pencere alt dizileri O(n) zamanda ve O(1) alan kullanarak sayar.

Python

def subarraySum(nums, k):
    # Kodu buraya yazın

Test durumları

Durum 1

Durum 2

Durum 3

Girdi

nums = [3, 4, -7, 1, 3, 3, 1, -4]
k = 7

Beklenen