Demo önizleme: Bu çözümler otomatik test paketini geçiyor ama insan tarafından incelenmedi. Trade-off ve yazıları taslak olarak değerlendirin.

Easyhashing

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

Doğrulanmadı

Zaman O(n)Alan 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.

Çözüm

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

Doğrulanmadı

Zaman O(n²)Alan 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.

Çözüm

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

Tamamlayıcıyı target - x olarak map’te aramak 90 saniyede hashing’i nasıl seçtirir?
Değeri kaydetmeden önce mi sonra mı bakarsın? Aynı indeksi iki kez kullanmayı hangi girdi yakalar?
Tek çözüm garantisi kalkarsa indeks sırası ve yinelenen çiftler nasıl değişir?