Longest Subarray with Sum K

+10

Tam sayılardan oluşan nums dizisi ve k hedefi verildiğinde, elemanlarının toplamı tam olarak k olan en uzun alt dizinin uzunluğunu döndürün. Alt dizi, ardışık elemanlardan oluşan ve en az bir eleman içeren bir dizidir. Bazı değerler sıfır veya sıfırdan küçük olabilir. Toplamı k olan bir alt dizi yoksa 0 döndürün.

Fonksiyon

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

numsinteger-array: negatifler ve sıfırlar dahil aranacak tam sayılar
kinteger: alt dizinin sahip olması gereken tam toplam
Döndürürinteger: toplamı k olan en uzun alt dizinin uzunluğu; böyle bir alt dizi yoksa 0

Kısıtlar

1 ≤ nums.length ≤ 2 × 10⁴
-10⁴ ≤ nums[i] ≤ 10⁴
-10⁹ ≤ k ≤ 10⁹
Her önek toplamı -2 × 10⁸ ile 2 × 10⁸ arasında kalır; bu nedenle 32 bitlik tamsayılar yeterlidir.
Hiçbir alt dizi toplamı k etmiyorsa 0 döndürün.

Örnekler

Girdi: nums = [2, -1, 3, 1, -4, 2, 3]k = 5
Çıktı: 5
Açıklama: Üç çalıştırmanın toplamı 5 eder: sondaki [2, 3], baştaki [2, -1, 3, 1] ve 2 ile 6. indeksler arasındaki [3, 1, -4, 2, 3]. Sonuncusu 5 öğeyle en uzun olanıdır.

Girdi: nums = [4, 1, 1, 2, -1, 1]k = 3
Çıktı: 4
Açıklama: [1, 1, 2, -1] 1'den 4'e kadar olan indekslerde ve [1, 2, -1, 1] 2'den 5'e kadar olan indekslerde, her ikisi de 4 elemanla 3 eder. Bir uzunluk döndürüyorsun, bu yüzden eşitlik önemli değil.

Ek soru

Negatif değerlere de izin verildiğinde, toplamı en fazla k olan en uzun alt diziyi nasıl bulursunuz?

İpuçları

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

3 ipucundan 0 açıldı

Çözüm

Kümülatif toplamlar, herhangi bir alt dizinin toplamını tek bir çıkarma işlemine dönüştürür: s indeksinden sonraki ve i indeksine kadar olan elemanların toplamı prefix[i] - prefix[s] olur. Her toplamın ilk göründüğü indeksi hatırlayın; tek bir geçişte her konumda biten en uzun eşleşme bulunur.

Her başlangıç noktasından başlayarak her alt diziyi genişlet

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

Sezgi

Her başlangıç noktasından sağa doğru ilerleyin ve her öğeyi birikimli toplama ekleyin. Toplam k değerine eşit olduğunda uzunluğu kaydedin. Her alt dizi bir başlangıç ve bitiş çifti olduğundan hiçbirini kaçırmazsınız. Toplam k değerini aştıktan sonra da ilerlemeye devam edin: ilk örnekte 2. indexten başlayınca toplamlar 3, 4, 0, 2, 5 olur ve sonuncunun 5'e ulaşmasının nedeni -4'tür.

Yaklaşık n²/2 çift vardır: n = 2 × 10^4 için 2 × 10^8 toplama işlemi.

Algoritma

best değerini 0 olarak ayarla.
Her start için total değerini 0 olarak ayarla.
end değerini start konumundan son indekse kadar ilerlet ve nums[end] değerini total değerine ekle.
total, k değerine eşit olduğunda best değerini best ile end - start + 1 değerlerinden büyük olanı olarak ayarla.
best değerini döndür.

def longestSubarrayWithSumK(nums, k):
    n = len(nums)
    best = 0
    for start in range(n):
        total = 0
        for end in range(start, n):
            total += nums[end]
            # A match may come after the total has passed k, so never stop early
            if total == k and end - start + 1 > best:
                best = end - start + 1
    return best

Her toplamın ilk indeksiyle önek toplamları

Sezgi

i indeksinde biten bir alt dizi toplamı, daha önceki bir toplam prefix - k değerine eşitse tam olarak k olur. Birden fazla önceki toplam koşulu sağlıyorsa, en uzun alt diziyi ilk olan başlatır; bu nedenle eşleme, her toplamı yalnızca ilk kez göründüğünde kaydeder. Daha sonraki bir eşleşme yalnızca daha kısa bir alt dizi başlatabilir. Toplam 0 değerini -1 indeksinde eşlemeye ekleyin; böylece 0 indeksinde başlayan bir eşleşme i + 1 uzunluğunda olur.

İlk örnekte toplamlar 2, 1, 4, 5, 1, 3, 6 şeklindedir. 6 indeksinde, 6 - 5 = 1 ilk kez 1 indeksinde görülmüştür; bu da 5 uzunluğunu verir. 1 toplamı 4 indeksinde yeniden görülür ve 1 indeksini korumak bu alt diziyi bulmamızı sağlar.

Her eleman için bir arama yapılması O(n) zaman alır ve eşleme en fazla n + 1 toplam tutar.

Algoritma

-1 indeksinde toplamı 0 olan bir first eşlemesi oluştur ve prefix ile best değerlerini 0 olarak ayarla.
Her i indeksi için nums[i] değerini prefix değerine ekle.
prefix - k eşlemede start indeksinde bulunuyorsa, best değerini best ile i - start değerlerinden büyük olanına ayarla.
prefix henüz eşlemede yoksa, i indeksiyle birlikte eşlemeye ekle.
best değerini döndür.

def longestSubarrayWithSumK(nums, k):
    # first[p] is the index where the prefix sum p first appears; the empty prefix sits at -1
    first = {0: -1}
    prefix = 0
    best = 0
    for i, num in enumerate(nums):
        prefix += num
        # The earliest prefix equal to prefix - k starts the longest match that ends at i
        start = first.get(prefix - k)
        if start is not None and i - start > best:
            best = i - start
        # Keep the first index only: a later one could only start a shorter subarray
        if prefix not in first:
            first[prefix] = i
    return best

Tuzaklar ve uç durumlar

Toplam her tekrarlandığında saklanan indeksi üzerine yazmak, en son başlangıç konumunu tutar ve daha kısa bir eşleşme bulur. İlk örnek 5 yerine 4 döndürür, çünkü toplam 1, 1. indeksten 4. indekse taşınır.
Toplamı k değerinden büyükken küçülen bir pencere de ilk örnekte 4 döndürür. Pencere, toplamı 4 olan [-1, 3, 1, -4, 2, 3] dizisini içererek sona erer ve -1'i hiç çıkarmaz.
0. indekste -1 toplamını dışarıda bırakmak, 0. indekste başlayan tüm eşleşmeleri kaçırır: [5, 0, 0, 0] için k = 5, 4 yerine 0 döndürür.
Saklanan indeks, alt diziden önceki konumdur; bu nedenle uzunluk i - start olur. 1 eklemek, bir fazla eleman sayar.

Sıkça sorulan sorular3

Toplamı K olan En Uzun Alt Dizinin zaman karmaşıklığı nedir?

Çalışan toplamlar ve ilk indeksleri tutan bir haritayla O(n) zaman ve O(n) ek alan: her öğe için bir arama ve en fazla bir ekleme. Her başlangıç noktasından tüm alt dizileri genişletmek O(n²) zaman ve O(1) alan gerektirir.

Bir dizide negatif sayılar olduğunda kayan pencere neden başarısız olur?

Kayan pencere, bir eleman eklemenin toplamı artırdığını ve bir elemanı çıkarmanın toplamı azalttığını varsayar. Negatif değerlerle, toplamı çok büyük olan bir pencere negatif bir eleman geldiğinde yine de k değerine ulaşabilir; toplamı çok küçük olan bir pencerenin ise solundaki negatif bir elemanı çıkarması gerekebilir. Pencere, hangi hamlenin doğru olduğunu anlayamaz.

Toplamı K olan en uzun alt dizi, O(1) ek alanla çözülebilir mi?

Yalnızca hiçbir değer negatif olmadığında. O zaman pencere büyüdükçe toplam asla azalmaz ve iki işaretçi, toplamı k olan en uzun pencereyi O(n) zamanda ve O(1) alan kullanarak bulur. Negatif değerler olduğunda, toplamlar haritasına ya da O(n²) taramasına ihtiyacın vardır.

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

Test #1

Test #2

Test #3

Argümanlar

nums = [2, -1, 3, 1, -4, 2, 3]
k = 5

Beklenen Çıktı