Two Sum

Problem (yeniden ifade)

Bir tamsayı dizisi nums ve bir tamsayı target verildiğinde, toplamı target olan iki sayının indekslerini döndür. Tam olarak bir çözüm vardır; aynı elemanı iki kez kullanamazsın.

Sezgi

İç içe döngü O(n²). Her x değeri için target-x gerekir. value→index hash map bu aramayı O(1) yapar.

Yaklaşımlar

Tek geçişli hash map

Verified

Time O(n)Space O(n)

Fikir. Soldan sağa tara. Her nums[i] için target-nums[i] daha önce görüldüyse o indeksleri döndür. Aksi halde nums[i]→i sakla.

Yürüyüş. nums=[2,7,11,15], target=9. 2 gör → sakla. 7 gör, 2 lazım, 0’da bulundu → [0,1].

Trade-off. Ortalama zamanda optimal. O(n) bellek kullanır. Kaba kuvvet yalnızca çok küçük n için uygundur.

Solution

export function twoSum(nums: number[], target: number): number[] {
  const seen = new Map<number, number>();
  for (let i = 0; i < nums.length; i++) {
    const need = target - nums[i]!;
    if (seen.has(need)) return [seen.get(need)!, i];
    seen.set(nums[i]!, i);
  }
  throw new Error("No solution");
}

export function twoSum(nums: number[], target: number): number[] {
  const seen = new Map<number, number>();
  for (let i = 0; i < nums.length; i++) {
    const need = target - nums[i]!;
    if (seen.has(need)) return [seen.get(need)!, i];
    seen.set(nums[i]!, i);
  }
  throw new Error("No solution");
}

Kaba kuvvet

Verified

Time O(n²)Space O(1)

Fikir. i < j olan her (i,j) çiftini dene.

Yürüyüş. Toplam target’a eşit olana kadar tüm çiftleri karşılaştır.

Trade-off. Ekstra bellek yok ama büyük n için çok yavaş. Doğruluk için iyi bir taban çözüm.

Solution

export function twoSumBrute(nums: number[], target: number): number[] {
  for (let i = 0; i < nums.length; i++) {
    for (let j = i + 1; j < nums.length; j++) {
      if (nums[i]! + nums[j]! === target) return [i, j];
    }
  }
  throw new Error("No solution");
}

export function twoSumBrute(nums: number[], target: number): number[] {
  for (let i = 0; i < nums.length; i++) {
    for (let j = i + 1; j < nums.length; j++) {
      if (nums[i]! + nums[j]! === target) return [i, j];
    }
  }
  throw new Error("No solution");
}

Şablon bağlantısı

Bu, Hashing şablonundaki klasik tamamlayıcı (complement) aramasıdır.

Yansıma

Hangi pattern bunu 90 saniye içinde ele verdi?
Standart şablondan ne değişti?
Pencere/işaretçi mantığındaki dikkatsiz bir off-by-one’ı hangi girdi bozar?