LeetCode 209: Minimum Boyuttaki Alt Dizi Toplamı – JavaScript Çözümü

LeetCode 209: Minimum Boyuttaki Alt Dizi Toplamı – JavaScript Çözümü

LeetCode’da sıkça karşılaştığımız zorlu problemlerden biri olan “Minimum Boyuttaki Alt Dizi Toplamı” (Minimum Size Subarray Sum) problemini ele alacağız. Bu problemde, verilen bir sayı dizisinde, toplamı belirli bir hedef değeri (target) aşan veya ona eşit olan en küçük alt dizinin uzunluğunu bulmamız gerekiyor. Örneğin, dizi [2,3,1,2,4,3] ve hedef değer 7 ise, en küçük alt dizi [4,3] olur ve uzunluğu 2’dir.

Bu problemi çözmek için birkaç farklı yaklaşım kullanılabilir. Ancak en verimli çözümler genellikle “Kayan Pencere” (Sliding Window) algoritmasını kullanır. Bu yöntem, iki işaretçi (başlangıç ve bitiş) ile dizide gezinerek, alt dizinin toplamını sürekli olarak günceller. Toplam hedef değere ulaştığında veya aştığında, alt dizinin uzunluğunu hesaplar ve minimum uzunluğu günceller. Daha sonra, başlangıç işaretçisini hareket ettirerek, alt dizinin boyutunu küçültmeye çalışır ve işlemi tekrarlar.

Kayan Pencere Algoritması ile Çözüm

İşte JavaScript kullanılarak Kayan Pencere algoritması ile yazılmış bir çözüm:

/**
 * @param {number} target
 * @param {number[]} nums
 * @return {number}
 */
var minSubArrayLen = function(target, nums) {
    let minLen = Infinity;
    let windowStart = 0;
    let windowSum = 0;

    for (let windowEnd = 0; windowEnd < nums.length; windowEnd++) {
        windowSum += nums[windowEnd];

        while (windowSum >= target) {
            minLen = Math.min(minLen, windowEnd - windowStart + 1);
            windowSum -= nums[windowStart];
            windowStart++;
        }
    }

    return minLen === Infinity ? 0 : minLen;
};

Bu kodda, windowStart ve windowEnd işaretçileri ile kayan pencere oluşturulur. windowSum değişkeni, pencerenin içindeki sayıların toplamını tutar. Döngü, pencere içindeki toplamın hedef değeri aşana kadar devam eder. Hedef değere ulaşıldığında veya geçildiğinde, minimum uzunluk güncellenir ve başlangıç işaretçisi hareket ettirilerek pencere küçültülür.

Performans Analizi

Kayan Pencere algoritmasının zaman karmaşıklığı O(n) iken, brute-force yaklaşımların zaman karmaşıklığı O(n^2) olur. Bu, özellikle büyük girdiler için Kayan Pencere algoritmasının çok daha verimli olduğunu gösterir. Bellek karmaşıklığı ise O(1)’dir, yani kullanılan bellek miktarı girdi boyutundan bağımsızdır.

Bu problem, algoritma ve veri yapıları bilginizi geliştirmek için harika bir pratik örneğidir. Daha fazla algoritma ve çözüm için fatihsoysal.com sitesini ziyaret edebilirsiniz.

Diğer çözüm yaklaşımları ve daha detaylı analizler için buraya bakabilirsiniz.

#Etiketler
leetcode, javascript, algoritma, programlama, minimum alt dizi toplamı, sliding window, iki işaretçi, fatihsoysal, kayan pencere, performans analizi, javascript çözümü