İçeriğe atla
ΣDSA Patterns
Menü
KalıplarProblemlerŞablonlarYol haritasıKaynaklarTekrarlarHakkında
Dil
EnglishTürkçe

İki İşaretçi

Rehber 4 / 6 · Yol 4 / 6

← ÖncekiSonraki →

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)

Toplamı target olan tüm benzersiz dörtlüleri döndür.

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

Tested only
Time O(n³)Space 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.

Solution
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;
}

Yansıma