3Sum Closest

Problem (yeniden ifade)

Bir tamsayı dizisi nums ve tamsayı target verildiğinde, toplamı target’a en yakın olan üç tamsayıyı bul. O toplamı döndür.

Sezgi

Sırala, bir indeksi sabitle, en yakın toplamı izlerken geri kalanı two pointers ile tara. 3Sum ile aynı omurga.

Yaklaşımlar

export function threeSumClosest(nums: number[], target: number): number {
  nums = [...nums].sort((a, b) => a - b);
  let best = nums[0]! + nums[1]! + nums[2]!;
  for (let i = 0; i < nums.length - 2; i++) {
    let lo = i + 1, hi = nums.length - 1;
    while (lo < hi) {
      const s = nums[i]! + nums[lo]! + nums[hi]!;
      if (Math.abs(s - target) < Math.abs(best - target)) best = s;
      if (s === target) return s;
      if (s < target) lo++; else hi--;
    }
  }
  return best;
}

export function threeSumClosest(nums: number[], target: number): number {
  nums = [...nums].sort((a, b) => a - b);
  let best = nums[0]! + nums[1]! + nums[2]!;
  for (let i = 0; i < nums.length - 2; i++) {
    let lo = i + 1, hi = nums.length - 1;
    while (lo < hi) {
      const s = nums[i]! + nums[lo]! + nums[hi]!;
      if (Math.abs(s - target) < Math.abs(best - target)) best = s;
      if (s === target) return s;
      if (s < target) lo++; else hi--;
    }
  }
  return best;
}

Şablon bağlantısı

Sırala + two pointers 3Sum omurgası; tam sıfır toplamak yerine en yakın toplamı tut.

Yansıma

• 3Sum ile aynı iskelet; hedef 0 değil target, kayıt üçlü değil toplam.
• abs(sum - target) güncellemesini her L,R çiftinde yaptın mı, yoksa yalnızca eşitlikte mi?
• Tam isabet (sum == target) erken çıkış yasal mı?