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

Mediumtwo-pointers

Two Sum II. Input Array Is Sorted

Problem (yeniden ifade)

1-indeksli sıralı bir tamsayı dizisi verildiğinde, target’a toplanan iki sayıyı bul. 1-tabanlı indekslerini döndür. Tam olarak bir çözüm vardır.

Sezgi

Sıralı düzen, büyük ucun toplamı azaltmasına ve küçük ucun artırmasına izin verir. iki uçtan tek geçiş.

Yaklaşımlar

İki uçtan two pointers

Doğrulanmadı

Zaman O(n)Alan O(1)

Fikir. lo başta, hi sonda. Toplam çok küçükse lo++. Çok büyükse hi–. Değilse 1-tabanlı indeksleri döndür.

Yürüyüş. numbers=[2,7,11,15], target=9 → 2+15 çok büyük, 2+11 çok büyük, 2+7=9 → [1,2].

Trade-off. Girdi sıralı ve sabit ek alan gerektiğinde hash map’ten daha hızlı.

Çözüm

export function twoSum(numbers: number[], target: number): number[] {
  let lo = 0, hi = numbers.length - 1;
  while (lo < hi) {
    const s = numbers[lo]! + numbers[hi]!;
    if (s === target) return [lo + 1, hi + 1];
    if (s < target) lo++;
    else hi--;
  }
  return [-1, -1];
}

export function twoSum(numbers: number[], target: number): number[] {
  let lo = 0, hi = numbers.length - 1;
  while (lo < hi) {
    const s = numbers[lo]! + numbers[hi]!;
    if (s === target) return [lo + 1, hi + 1];
    if (s < target) lo++;
    else hi--;
  }
  return [-1, -1];
}

Şablon bağlantısı

Sıralı two-sum: karşıt uç two pointers, hash map gerekmez.

Yansıma

Sıralı girdi hashing’i neden gereksiz kılar? 1-tabanlı indeks off-by-one’ı nerede?
Aynı değeri iki kez kullanamazsın: L ve R çakışınca ne yaparsın?
Two Sum I (hash) şablonunu burada kullanırsan sıralılık ipucunu çöpe atmış olursun.