LeetCode 15: 3Sum JavaScript Çözümü
Bu makalede, LeetCode’un popüler problemlerinden biri olan “3Sum” problemine JavaScript ile nasıl çözüm üretebileceğinizi detaylı olarak ele alacağız. Hedefimiz, verilen bir dizide toplamı sıfıra eşit olan üç sayının tüm olası kombinasyonlarını bulmak. Bu problem, algoritma ve veri yapıları bilginizi test eden zorlu bir problemdir. Ancak doğru yaklaşımla, verimli bir çözüm geliştirmek mümkündür.
Problemin Anlatımı
Verilen bir tam sayı dizisi nums, toplamı sıfıra eşit olan üç sayının tüm olası, benzersiz kombinasyonlarını bulun. Her kombinasyon, artan sırada listelenmelidir. Örneğin, nums = [-1, 0, 1, 2, -1, -4] için, çıktı [[-1, -1, 2], [-1, 0, 1]] olmalıdır.
Çözüm Yöntemi: İki İşaretçi Tekniği
Bu problemi çözmek için en verimli yöntemlerden biri, iki işaretçi tekniğini kullanmaktır. Öncelikle, diziyi sıralayarak başlıyoruz. Ardından, dizideki her bir elemanı ele alıp, hedef toplamı (0) elde etmek için kalan iki sayıyı bulmak üzere iki işaretçi kullanıyoruz. Bu işaretçiler, sıralı dizinin kalan kısmında ilerleyerek, toplamı sıfıra eşit olan kombinasyonları arar. Bu yaklaşım, çözümü O(n^2) zaman karmaşıklığı ile gerçekleştirir, bu da oldukça verimlidir. Ayrıca, benzersiz kombinasyonları bulmak için ek kontroller eklememiz gerekir.
JavaScript Kodu
/**
* @param {number[]} nums
* @return {number[][]}
*/
var threeSum = function(nums) {
nums.sort((a, b) => a - b); // Dizinin sıralanması
const result = [];
for (let i = 0; i < nums.length - 2; i++) {
// Tekrar eden sayıları atlamak için
if (i > 0 && nums[i] === nums[i - 1]) continue;
let left = i + 1;
let right = nums.length - 1;
while (left < right) {
const sum = nums[i] + nums[left] + nums[right];
if (sum === 0) {
result.push([nums[i], nums[left], nums[right]]);
// Tekrar eden sayıları atlamak için
while (left < right && nums[left] === nums[left + 1]) left++;
while (left < right && nums[right] === nums[right - 1]) right--;
left++;
right--;
} else if (sum < 0) {
left++;
} else {
right--;
}
}
}
return result;
};
Kod Açıklaması
Kod öncelikle diziyi sıralar. Sonrasında, dış döngü, dizinin her bir elemanını teker teker inceler. İç döngü ise, iki işaretçi (left ve right) kullanarak, toplamı sıfıra eşit olan kombinasyonları arar. Eğer toplam sıfırdan küçükse, left işaretçisi sağa kaydırılır; toplam sıfırdan büyükse, right işaretçisi sola kaydırılır. Benzersiz kombinasyonlar bulmak için gerekli kontroller de eklenmiştir. Sonuç olarak, tüm benzersiz üçlü kombinasyonlar döndürülür.
Karmaşıklık Analizi
Bu çözümün zaman karmaşıklığı O(n^2) ve yer karmaşıklığı O(1)’dir (yerinde sıralama varsayımıyla). Sıralama işlemi O(n log n) zaman alırken, iki işaretçi döngüsü O(n^2) zaman alır. Ancak, sıralama işlemi genel zaman karmaşıklığına baskın gelmez, çünkü iki işaretçi tekniği O(n^2) zaman almaktadır.
Sonuç
Bu makalede, LeetCode 3Sum problemini çözmek için verimli bir JavaScript çözümü sunduk. İki işaretçi tekniği kullanarak, problemi O(n^2) zaman karmaşıklığı ile çözebildik. Umarım bu makale, algoritma ve veri yapıları becerilerinizi geliştirmenize yardımcı olur. Daha fazla algoritma çözümü ve yazılım geliştirme ipuçları için fatihsoysal.com adresini ziyaret edebilirsiniz.
Faydalı Kaynaklar:
#Etiketler
#LeetCode #3Sum #JavaScript #Algoritma #VeriYapıları #İkiİşaretçiTekniği #Programlama #Çözüm #YazılımGeliştirme #FatihSoysal