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

4Sum

Problem (yeniden ifade)

Bir tamsayı dizisi nums ve bir target verildiğinde, toplamı target olan tüm benzersiz dörtlüleri [a,b,c,d] döndür. Sıra grupları ayırmaz; değer kümesi tektir.

Sezgi

k-sum genellemesi: sırala, iki indeksi sabitle, geri kalanı two pointers ile tara; yinelenenleri atla.

Yaklaşımlar

Sırala + iç içe two pointers

Doğrulanmadı

Zaman O(n³)Alan O(1)

Fikir. İç içe i,j ile lo/hi; benzersiz dörtlüler için eşit komşuları atla.

Yürüyüş. [1,0,-1,0,-2,2], target=0 → üç benzersiz dörtlü.

Trade-off. O(n³) standarttır; pair-hash daha fazla bellek kullanır.

Çözüm

export function fourSum(nums: number[], target: number): number[][] {
  nums = [...nums].sort((a, b) => a - b);
  const res: number[][] = [];
  const n = nums.length;
  for (let i = 0; i < n - 3; i++) {
    if (i > 0 && nums[i] === nums[i - 1]) continue;
    for (let j = i + 1; j < n - 2; j++) {
      if (j > i + 1 && nums[j] === nums[j - 1]) continue;
      let lo = j + 1, hi = n - 1;
      while (lo < hi) {
        const s = nums[i]! + nums[j]! + nums[lo]! + nums[hi]!;
        if (s === target) {
          res.push([nums[i]!, nums[j]!, nums[lo]!, nums[hi]!]);
          lo++; hi--;
          while (lo < hi && nums[lo] === nums[lo - 1]) lo++;
          while (lo < hi && nums[hi] === nums[hi + 1]) hi--;
        } else if (s < target) lo++; else hi--;
      }
    }
  }
  return res;
}

export function fourSum(nums: number[], target: number): number[][] {
  nums = [...nums].sort((a, b) => a - b);
  const res: number[][] = [];
  const n = nums.length;
  for (let i = 0; i < n - 3; i++) {
    if (i > 0 && nums[i] === nums[i - 1]) continue;
    for (let j = i + 1; j < n - 2; j++) {
      if (j > i + 1 && nums[j] === nums[j - 1]) continue;
      let lo = j + 1, hi = n - 1;
      while (lo < hi) {
        const s = nums[i]! + nums[j]! + nums[lo]! + nums[hi]!;
        if (s === target) {
          res.push([nums[i]!, nums[j]!, nums[lo]!, nums[hi]!]);
          lo++; hi--;
          while (lo < hi && nums[lo] === nums[lo - 1]) lo++;
          while (lo < hi && nums[hi] === nums[hi + 1]) hi--;
        } else if (s < target) lo++; else hi--;
      }
    }
  }
  return res;
}

Şablon bağlantısı

Sıralı dizide k-sum: iki indeksi sabitle, kalanı two-pointer (3Sum + bir iç döngü).

Yansıma

3Sum’a bir dış döngü daha. n⁴ kaba kuvvetten n³’e inmek için sıralama şart mı?
Dört aynı değer, target onların toplamı: bir kere mi, sıfır mı?
Taşma: dört 10^9 toplamı 32-bit int’te kırılır mı? (C# / TS int32.)