LeetCode 209: Minimum Boyuttaki Alt Dizi Toplamı
Bu makalede, LeetCode’un popüler problemlerinden biri olan “Minimum Size Subarray Sum” (Minimum Boyuttaki Alt Dizi Toplamı) problemine farklı açılardan bakacağız. Problem, verilen bir dizide toplamı hedef değeri (target) aşan veya ona eşit olan en küçük alt dizinin boyutunu bulmayı gerektiriyor. Örneğin, dizi [2,3,1,2,4,3] ve hedef değer 7 ise, en küçük alt dizi [4,3] olup boyutu 2’dir.
Bu problemi çözmek için birkaç farklı yaklaşım mevcuttur. Bunlardan en yaygın olanları brüt kuvvet yöntemi, iki işaretçi yöntemi (veya slayan pencere tekniği) ve ikili arama yöntemidir. Ancak, performans açısından en etkili yöntem, iki işaretçi yöntemidir.
Brüt Kuvvet Yöntemi
Brüt kuvvet yöntemi, dizinin tüm olası alt dizilerini kontrol ederek çalışır. Bu yöntem oldukça basit olmakla birlikte, zaman karmaşıklığı O(n^2) olduğu için büyük dizilerde oldukça yavaştır. Bu nedenle, büyük ölçekli problemler için pratik değildir. Ancak, algoritmanın mantığını anlamak için iyi bir başlangıç noktası olabilir.
İki İşaretçi (Slayan Pencere) Yöntemi
İki işaretçi yöntemi (veya slayan pencere tekniği), daha verimli bir çözüm sunar. Bu yöntemde, iki işaretçi (başlangıç ve bitiş işaretçileri) kullanarak, dizide bir pencere oluştururuz. Pencerenin toplamı hedef değeri aşana kadar sağ işaretçiyi (bitiş işaretçisi) sağa doğru kaydırırız. Hedef değere ulaştığımızda veya aştığımızda, pencerenin boyutunu kontrol eder ve minimum boyutu güncelleriz. Sonrasında, sol işaretçiyi (başlangıç işaretçisi) sağa kaydırarak pencerenin boyutunu küçültür ve işlemi tekrar ederiz. Bu işlem, sağ işaretçi dizinin sonuna gelene kadar devam eder. Bu yöntemin zaman karmaşıklığı O(n)’dir.
def minimum_subarray_sum(nums, target):
min_length = float('inf')
left = 0
current_sum = 0
for right, num in enumerate(nums):
current_sum += num
while current_sum >= target:
min_length = min(min_length, right - left + 1)
current_sum -= nums[left]
left += 1
return min_length if min_length != float('inf') else 0
Yukarıdaki Python kodunda, float('inf') sonsuzluğu temsil eder. Bu sayede, hiçbir alt dizinin toplamının hedef değere ulaşmadığı durumlarda 0 değerini dönebiliriz.
Optimizasyonlar ve İpuçları
İki işaretçi yöntemini daha da optimize edebiliriz. Örneğin, dizinin negatif sayılar içermesi durumunda, hedef değerden küçük bir toplam elde etsek bile sağ işaretçiyi kaydırmaya devam etmeliyiz. Çünkü daha sonra negatif sayıların toplamı pozitif bir sayı ile karşılaşınca hedef değeri aşabiliriz. Ayrıca, kodun okunabilirliğini ve performansını iyileştirmek için çeşitli küçük değişiklikler yapabiliriz.
Bu problem için, verimli bir çözüm bulmanın önemi büyüktür. Bu nedenle, iki işaretçi yöntemini anlamak ve uygulamak önemlidir. Daha fazla algoritma ve veri yapıları hakkında bilgi edinmek için fatihsoysal.com sitesini ziyaret edebilirsiniz.
Başka faydalı kaynaklar:
#Etiketler: LeetCode, 209, Minimum Boyuttaki Alt Dizi Toplamı, Algoritma, Programlama, Python, İki İşaretçi, Slayan Pencere, Optimizasyon, Brüt Kuvvet, Alt Dizi, Toplam