Minimum Size Subarray Sum

Q: Minimum Boyutlu Alt Dizi Toplamı'nın zaman karmaşıklığı nedir?

Kayan pencere çözümü O(n) zamanda ve O(1) alanda çalışır. İç döngü, algoritmanın karesel zamanda çalışmasına yol açacakmış gibi görünür, ancak left yalnızca ileri doğru hareket eder; bu nedenle tüm çalışma boyunca en fazla n kez ilerler. Önek toplamı sürümü O(n log n) zamandadır ve her başlangıç noktasını kontrol etmek O(n²) zaman alır.

Q: O(n) varken O(n log n) önek toplamı çözümünü neden öğrenelim?

Mülakat yapanlar genellikle O(n) yanıtından sonra bunu sorar. Bu, pozitif değerlerin ikinci bir kullanımını gösterir: önek toplamları sıralıdır, bu nedenle ikili arama, kümülatif toplamın bir eşiği ilk kez aştığı yeri bulur. Bu araç, ağırlığıyla orantılı olarak rastgele bir indeks seçmek gibi başka problemlerde de karşımıza çıkar.

Q: Alt dizinin toplamı tam olarak target değerine eşit olmak zorunda mı?

Hayır. target değerine eşit veya ondan büyük olan her toplam sayılır. target = 15 için 9, 3, 7 penceresinin toplamı 19’dur ve uzunluğu hâlâ 3’tür. Bunun yerine tam bir toplam gerekiyorsa pencere pozitif değerler için yine işe yarar: toplam hedefin üzerindeyken pencereyi daraltın ve yalnızca toplam eşit olduğunda uzunluğu kaydedin.

OrtaKayan pencere Önek toplamı

+10

Pozitif bir tamsayı olan target ve pozitif tamsayılardan oluşan bir nums dizisi veriliyor. Toplamı en az target olan en kısa alt diziyi (yan yana gelen elemanlardan oluşan bir dizi parçasını) bulun ve uzunluğunu döndürün. Hiçbir alt dizinin toplamı target değerine ulaşmıyorsa 0 döndürün.

Fonksiyon

minSubArrayLen(target: integer, nums: integer-array) → integer

targetinteger: bir alt dizinin ulaşması veya geçmesi gereken toplam
numsinteger-array: pozitif tam sayılar dizisi
Döndürürinteger: Toplamı en az target olan en kısa alt dizinin uzunluğu; böyle bir alt dizi yoksa 0

Kısıtlar

1 ≤ target ≤ 10⁹
1 ≤ nums.length ≤ 2 × 10⁴
1 ≤ nums[i] ≤ 10⁴

Örnekler

Girdi: target = 15nums = [4, 2, 9, 3, 7, 1, 5]
Çıktı: 3
Açıklama: Hiçbir iki komşu 15'e ulaşmaz: en büyük çift 9 + 3 = 12'dir. Üç komşu ulaşır: 4 + 2 + 9 = 15 ve 9 + 3 + 7 = 19, bu yüzden cevap 3'tür.

Gönderirken +16 gizli test

Ek soru

nums sıfırları ve negatif sayıları da içerebilseydi ve kayan pencere artık işe yaramasaydı, bunu nasıl çözerdin?

İpuçları

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

3 ipucundan 0 açıldı

Çözüm

Değerlerin tümü pozitiftir; bu nedenle bir alt diziyi genişletmek toplamını her zaman artırır, kısaltmak ise her zaman azaltır. Her iki hızlı çözümün temelinde bu tek gerçek yatar. Önek toplamları sıralı bir listeye dönüşür; böylece ikili arama, bir toplamın ilk kez target değerine ulaştığı yeri bulur. Daha da iyisi, başlangıç sağa kaydıkça en iyi bitiş noktası sola kaymaz; bu yüzden sağdan genişleyip soldan daralan tek bir pencere, yanıtı tek geçişte bulur.

Her başlangıçtan uzat

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

Sezgi

Bir başlangıç indeksi sabitle ve sağa doğru ilerleyerek değerleri birer birer ekle. Çalışan toplam ilk kez target değerine ulaştığında, bu başlangıçtan başlayan en kısa alt diziyi bulmuş olursun: daha kısa olanların her biri daha erken durmuş ve toplamları hâlâ çok küçük kalmıştır. Bu yüzden uzunluğunu kaydet, genişletmeyi bırak ve sonraki başlangıca geç. Yanıt, tüm başlangıçlar arasındaki en küçük uzunluktur.

target = 15 ve [4, 2, 9, 3, 7, 1, 5] için 0. başlangıçta toplamlar 4, 6, 15 olur ve uzunluk 3'te durur. 1. başlangıçta toplamlar 2, 11, 14, 21 olur ve uzunluk 4'te durur. 2. başlangıçta toplamlar 9, 12, 19 olur; uzunluk yine 3'tür. Hiçbir başlangıç 3'ten daha iyisini vermez.

Sorun, hedefe ulaşmanın zor olduğu durumlarda ortaya çıkar. Hiçbir alt dizi hedefe ulaşmazsa her başlangıç dizinin sonuna kadar ilerler: n(n+1)/2 toplama işlemi; bu, n = 2 × 10^4 için 2 × 10^8 işlem demektir. Ayrıca her başlangıç, önceki başlangıcın zaten hesapladığı toplamları yeniden hesaplar.

Algoritma

best değerini 0 olarak ayarla; bu, henüz hiçbir şey bulunmadığı anlamına gelir.
Her başlangıç indeksi için çalışan toplamı 0 olarak ayarla.
Bitiş indeksini başlangıçtan itibaren sağa ilerlet ve toplama nums[end] değerini ekle.
Toplam target değerine ulaştığında, best değerinden büyükse end-start+1 değerini sakla ve bu başlangıç için genişletmeyi durdur.
best değerini döndür.

def minSubArrayLen(target, nums):
    n = len(nums)
    best = 0  # 0 means no subarray found yet
    for start in range(n):
        total = 0
        for end in range(start, n):
            total += nums[end]
            if total >= target:
                # The shortest subarray from this start ends here
                if best == 0 or end - start + 1 < best:
                    best = end - start + 1
                break
    return best

Önek toplamları ve ikili arama

Sezgi

prefix[k], ilk k değerin toplamı olsun ve prefix[0] = 0 olsun. nums[start..end-1] toplamı o hâlde prefix[end] - prefix[start] olur. Sabit bir başlangıç için prefix[end] ≥ prefix[start] + target koşulunu sağlayan en küçük end değerini istiyorsun.

Tüm değerler pozitif olduğundan prefix kesin olarak artar ve belirli bir değere ulaştığı ilk konum ikili aramayla bulunabilir. [4, 2, 9, 3, 7, 1, 5] için prefix, [0, 4, 6, 15, 18, 25, 26, 31] olur. 2. başlangıç konumundan 6 + 15 = 21 gerekir; en az 21 olan ilk prefix değeri, 5. indeksteki 25'tir. Dolayısıyla pencere nums[2..4] = 9, 3, 7 olur ve uzunluğu 3'tür.

prefix[n] bile bir başlangıç için gereken değerin altındaysa, o başlangıç için hiçbir end işe yaramaz; prefix[start] yalnızca arttığından daha sonraki hiçbir başlangıç için de işe yaramaz. Bu noktada dur. Bu, n ikili arama, O(n log n) zaman ve prefix dizisi için O(n) ek maliyet demektir. Karşılaştırılan en büyük değer 2 × 10^8 + 10^9'dur ve 32 bitlik bir tamsayıya sığar.

Algoritma

n+1 uzunluğunda prefix oluştur; prefix[k+1] = prefix[k] + nums[k] olacak şekilde.
Her başlangıç için need = prefix[start] + target değerini hesapla.
prefix[n] < need ise dur: daha sonraki hiçbir başlangıç başarılı olamaz.
İlk prefix[end] ≥ need değerini bulmak için start+1 ile n arasındaki konumlarda ikili arama yap ve şimdiye kadarki en kısa uzunluk buysa end-start değerini sakla.
En kısa uzunluğu döndür; hiçbir başlangıç başarılı olmadıysa 0 döndür.

from bisect import bisect_left


def minSubArrayLen(target, nums):
    n = len(nums)
    # prefix[k] is the sum of the first k values; it only grows
    prefix = [0] * (n + 1)
    for i in range(n):
        prefix[i + 1] = prefix[i] + nums[i]
    best = 0
    for start in range(n):
        need = prefix[start] + target
        if prefix[n] < need:
            break  # no window from here on can reach target
        # The first end with prefix[end] >= need closes the shortest window
        end = bisect_left(prefix, need, start + 1)
        if best == 0 or end - start < best:
            best = end - start
    return best

Kaydırmalı pencere

Sezgi

Bir nums[left..right] penceresi ve toplamını tut. right değerini her seferinde bir adım ilerlet ve yeni değeri ekle. Toplam target değerine eşit veya ondan büyük olduğu sürece pencere bir adaydır: uzunluğunu kaydet, ardından nums[left] değerini çıkar ve daha kısa bir pencerenin hâlâ işe yarayıp yaramadığını görmek için left değerini ilerlet.

left neden kalıcı olarak pencereden çıkarılabilir? nums[left..right] penceresi target değerine ilk kez ulaştığında, daha küçük olan nums[left..right-1] penceresi bu değere ulaşmamıştır; çünkü önceki adımda döngü bu pencereyi küçültmüş olurdu. Dolayısıyla bu başlangıç için right en erken bitiş konumudur ve daha sonraki herhangi bir bitiş yalnızca daha uzun bir alt dizi verir. Bu başlangıç için elde edilebilecek en iyi yanıt bulunmuştur. Bu argüman pozitif değerlere ihtiyaç duyar: negatif bir sayı varsa daha uzun bir pencerenin toplamı sonradan daha büyük olabilir.

target = 15 ve [4, 2, 9, 3, 7, 1, 5] için: toplam 4, 6, 15 olarak yükselir; bu yüzden 3 uzunluğu kaydedilir ve 4 çıkar (11). 3 eklemek toplamı 14'e, 7 eklemek 21'e çıkarır: 4 uzunluğu kaydedilir, 2 çıkarılır (19), 3 uzunluğu kaydedilir, 9 çıkarılır (10). 1 ve 5 eklemek toplamı 16'ya çıkarır: 4 uzunluğu kaydedilir, 3 çıkarılır (13). Yanıt 3'tür.

while döngüsü for döngüsünün içinde yer alır; ancak her indeks pencereye bir kez girip bir kez çıktığından toplam işlem miktarı O(n) olur. Yalnızca üç sayı saklanır; dolayısıyla bellek kullanımı O(1)'dir.

Algoritma

left = 0, total = 0 ve best = 0 değerlerini ayarla.
Her right için nums[right] değerini total'a ekle.
total ≥ target olduğu sürece, right-left+1 değeri best'ten büyükse best olarak tut, nums[left] değerini çıkar ve left değerini bir adım sağa ilerlet.
Toplam hiçbir zaman target'a ulaşmadıysa hâlâ 0 olan best değerini döndür.

def minSubArrayLen(target, nums):
    best = 0  # 0 means no window found yet
    total = 0  # sum of nums[left .. right]
    left = 0
    for right in range(len(nums)):
        total += nums[right]
        # Shrink while the window still reaches target
        while total >= target:
            if best == 0 or right - left + 1 < best:
                best = right - left + 1
            total -= nums[left]
            left += 1
    return best

Tuzaklar ve uç durumlar

Hataların çoğu, pencereyi daraltma adımında ve hiçbir pencerenin toplamı target değerine ulaşmadığında döndürdüğünüz değerde ortaya çıkar.

while yerine if ile daraltma yapmak. target = 12 ve [1, 1, 2, 3, 12] için 12'yi eklemek toplamı 19 yapar. Bir if uzunluğu 5 olarak kaydeder, bir değeri kaldırır ve devam eder; böylece uzunluğu 1 olan [12] penceresi hiç ölçülmez. Bir döngü, toplam hâlâ yeterli olduğu sürece değerleri kaldırmaya devam eder.
nums[left] değerini kaldırdıktan sonra uzunluğu kaydetmek; bunu kaldırmadan önce yapmak gerekir. Ölçtüğünüz pencere, toplamı target değerine ulaşan pencere olmalıdır.
≥ yerine > ile karşılaştırma yapmak. Toplamı target değerine eşit olan bir alt dizi de sayılır: target = 9 için [3, 3, 3] dizisinin yanıtı 0 değil, 3'tür.
Sentinel değerini döndürmek. best değerini n+1 veya sonsuz olarak başlatırsanız, hiçbir pencerenin toplamı target değerine ulaşmadığında bu değeri 0'a dönüştürün.
Pencereyi sıfır veya negatif değerler içeren dizilerde yeniden kullanmak. Bu yöntem her değerin pozitif olmasına dayanır; bu problem bunu garanti eder, ancak farklı varyantlar etmez.

Sıkça sorulan sorular4

Minimum Boyutlu Alt Dizi Toplamı'nın zaman karmaşıklığı nedir?

Kayan pencere çözümü O(n) zamanda ve O(1) alanda çalışır. İç döngü, algoritmanın karesel zamanda çalışmasına yol açacakmış gibi görünür, ancak left yalnızca ileri doğru hareket eder; bu nedenle tüm çalışma boyunca en fazla n kez ilerler. Önek toplamı sürümü O(n log n) zamandadır ve her başlangıç noktasını kontrol etmek O(n²) zaman alır.

Kaydırmalı pencerenin neden pozitif sayılara ihtiyacı var?

Pencereyi küçültmek toplamını düşürmeli, büyütmek ise artırmalıdır; aksi takdirde soldaki elemanı çıkarmak yanıtın başlangıcını kaybettirebilir. Negatif sayılarda bu sıralama bozulur. Yaygın çözüm, aday başlangıçları tutan monoton bir deque ile önek toplamları kullanmaktır; bu yöntem yine O(n) sürede çalışır.

O(n) varken O(n log n) önek toplamı çözümünü neden öğrenelim?

Mülakat yapanlar genellikle O(n) yanıtından sonra bunu sorar. Bu, pozitif değerlerin ikinci bir kullanımını gösterir: önek toplamları sıralıdır, bu nedenle ikili arama, kümülatif toplamın bir eşiği ilk kez aştığı yeri bulur. Bu araç, ağırlığıyla orantılı olarak rastgele bir indeks seçmek gibi başka problemlerde de karşımıza çıkar.

Alt dizinin toplamı tam olarak target değerine eşit olmak zorunda mı?

Hayır. target değerine eşit veya ondan büyük olan her toplam sayılır. target = 15 için 9, 3, 7 penceresinin toplamı 19’dur ve uzunluğu hâlâ 3’tür. Bunun yerine tam bir toplam gerekiyorsa pencere pozitif değerler için yine işe yarar: toplam hedefin üzerindeyken pencereyi daraltın ve yalnızca toplam eşit olduğunda uzunluğu kaydedin.

Python

def minSubArrayLen(target, nums):
    # Kodu buraya yazın

Test durumları

Durum 1

Durum 2

Durum 3

Girdi

target = 15
nums = [4, 2, 9, 3, 7, 1, 5]

Beklenen

Minimum Size Subarray Sum

Fonksiyon

Kısıtlar

Örnekler

İpuçları

Çözüm

Her başlangıçtan uzat

Önek toplamları ve ikili arama

Kaydırmalı pencere

Tuzaklar ve uç durumlar

Sıkça sorulan sorular4

Benzer problemler