Toplamı k olan alt dizileri say

Problem

Bir tamsayı dizisi (negatif değerler olabilir) ve bir k değeri veriliyor. Dizinin boş olmayan, bitişik alt dizilerinden kaç tanesinin elemanları toplamı tam olarak k'ya eşit? Aynı değerleri içeren ama farklı konumlarda başlayan ya da biten alt diziler ayrı sayılır.

Girdi:  nums = [3, 4, 7, -2, 2, 1, 4, 2], k = 7
Çıktı:  6
        [3,4]  [7]  [7,-2,2]  [2,1,4]  [1,4,2]  [-2,2,1,4,2]

Girdi:  nums = [1, 1, 1], k = 2
Çıktı:  2

Netleştirme soruları

• Negatif sayılar ve sıfır olabilir mi? (Bu, kayan pencerenin işe yarayıp yaramayacağını belirler.)
• Sayı mı isteniyor, alt dizilerin kendisi mi?
• Boş alt dizi sayılır mı? (Hayır, sadece boş olmayanlar.)
• Toplamlar int'e sığar mı? (LeetCode sınırlarında evet: 2×10⁴ × 1000; genel çözümde long.)
• k negatif olabilir mi?

İpuçları

Yaklaşım

Brute force: Her başlangıç i için j'yi sağa ilerletip toplamı biriktir, k'ya eşitse say. O(n²) zaman, O(1) bellek. (Üç iç içe döngüyle toplamı her seferinde yeniden hesaplamak O(n³) olur; bu da sık yapılan bir hatadır.)

Neden kayan pencere çalışmaz? Kayan pencere, pencereyi büyütünce toplamın arttığı, küçültünce azaldığı monoton durumlarda çalışır. Negatif sayılar bu monotonluğu bozar: pencereyi genişletmek toplamı düşürebilir. Sadece pozitif sayılar olsaydı iki işaretçi yeterdi. Bu ayrımı adayın kendiliğinden söylemesi güçlü bir sinyaldir.

Optimal, önek toplamı + HashMap: P[j] ilk j elemanın toplamı olsun (P[0] = 0). i..j-1 alt dizisinin toplamı P[j] - P[i]. Bunun k olması için P[i] = P[j] - k gerekir. Diziyi soldan sağa gezerken o ana kadar gördüğün önek toplamlarını bir map'te say. Her yeni önek toplamında prefix - k değerinin kaç kez görüldüğünü sonuca ekle, sonra mevcut öneki map'e ekle.

{0: 1} başlangıcı kritik: dizinin en başından başlayan alt diziler (P[0] = 0 ile eşleşenler) aksi halde sayılmaz. [5], k = 5 örneği bunu hemen yakalar.

Sıra da önemli: önce say, sonra ekle. Tersini yaparsan k = 0 iken mevcut önek kendisiyle eşleşir ve boş alt diziyi saymış olursun.

Java çözümü

import java.util.HashMap;
import java.util.Map;

public final class SubarraySumEqualsK {

    public int subarraySum(int[] nums, int k) {
        Map<Long, Integer> prefixCount = new HashMap<>();          // önek toplamı -> kaç kez görüldü
        prefixCount.put(0L, 1);                                    // boş önek: baştan başlayan alt diziler için
        long prefix = 0;
        int count = 0;
        for (int num : nums) {
            prefix += num;
            count += prefixCount.getOrDefault(prefix - k, 0);      // prefix - önceki = k
            prefixCount.merge(prefix, 1, Integer::sum);
        }
        return count;
    }
}

Önek toplamını long tuttum; LeetCode sınırlarında int yeter ama genel bir dizi için Integer.MAX_VALUE toplamları taşar. Testte [MAX, MAX, -MAX] girdisi bunu doğrular.

Karmaşıklık

• Zaman: O(n) ortalama; her eleman için bir getOrDefault ve bir merge.
• Bellek: O(n); en kötü durumda tüm önek toplamları farklıdır.
• Brute force'a göre bellek karşılığında zaman kazanıyoruz; "O(n) bellekle O(n²)'den O(n)'e indim" cümlesi beklenen trade-off ifadesidir.

Kenar durumlar ve testler

main içinde derlenip çalıştırıldı; ayrıca 3.000 rastgele girdide (değerler -5..5, k -5..5) O(n²) brute force ile karşılaştırıldı.

Mülakatçı için

Meta'da çok sık geçen bu soru, adayın önek toplamı dönüşümünü bilip bilmediğini ve kayan pencereyi yanlış yerde kullanıp kullanmadığını ölçer. En yaygın hata, negatif sayıları görmezden gelip iki işaretçi yazmaktır; bu kod verilen pozitif örneklerde çalıştığı için aday hatayı fark etmez.

İpucu zamanlaması: Aday kayan pencere yazmaya başlarsa hemen durdurma; bitirip [3, 4, 7, -2, 2, 1, 4, 2] ile yürütmesini iste, hatayı kendi görsün. O(n²)'de takılırsa "aralık toplamını iki önek toplamıyla ifade edebilir misin?" de. {0: 1}'i unutursa [5], k = 5 örneğini ver.

Takip soruları:

1. Sayı yerine en uzun alt dizinin uzunluğu istenseydi? (Beklenen: map'te her önek toplamının ilk görüldüğü index; LeetCode 325.)
2. Toplamı k'nın katı olan alt diziler? (Beklenen: önek toplamını mod k ile tut, negatif modu düzelt; LeetCode 974 ve 523.)
3. Bu bir ödeme akışı: "Hesaptaki hareketlerden net toplamı tam 0 olan dönemleri bul." Veri milyonlarca satır ve veritabanındaysa? (Beklenen: SQL'de window function ile kümülatif toplam SUM(amount) OVER (ORDER BY ts) ve aynı kümülatif değere sahip satır çiftleri.)

Benzer problemler

• Two Sum (LeetCode 1): aynı "daha önce gördüm mü" kalıbı (bu sette: two-sum).
• Continuous Subarray Sum (LeetCode 523) ve Subarray Sums Divisible by K (LeetCode 974): mod ile önek toplamı.
• Maximum Size Subarray Sum Equals k (LeetCode 325).
• Minimum Size Subarray Sum (LeetCode 209): sadece pozitifler, kayan pencere çalışır.
• Path Sum III (LeetCode 437): aynı fikrin ağaç üzerindeki hali.