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

Closest Subsequence Sum

Problem (yeniden ifade)

nums (n ≤ 40) içinde toplamı goal’a mümkün olduğunca yakın bir alt dizi seç. Minimum mutlak farkı döndür.

Sezgi

2^40 imkânsız; 2^20 yaklaşık bir milyon. Böl, her yarıda tüm alt küme toplamlarını say (0 dahil), solu sırala, her sağ toplam için goal − right ikili ara.

Yaklaşımlar

Ortada buluş, en yakın alt küme toplamı

Doğrulanmadı

Zaman O(n·2^{n/2})Alan O(2^{n/2})

Fikir. 2^{n/2} sol toplam üret, sırala. Her sağ toplam r için goal − r’ye en yakın sol toplamı bul — need’den büyük olmayan en büyük (lo) ve lo+1. Boş alt dizi geçerli.

Yürüyüş. nums=[5,7,−3], goal=6: en yakın 5 veya 7 → fark 1. [1,2,3], goal=−7 → boş toplam 0, fark 7.

Trade-off. Solu hash’lemek yalnızca tam isabeti kolaylaştırır; en yakın için sıralı liste ve ekleme noktasının iki komşusu gerekir.

Çözüm

export function minAbsDifference(nums: number[], goal: number): number {
  const mid = nums.length >> 1;
  const left = nums.slice(0, mid);
  const right = nums.slice(mid);

  const allSums = (arr: number[]): number[] => {
    const sums = [0];
    for (const v of arr) {
      const n = sums.length;
      for (let i = 0; i < n; i++) sums.push(sums[i]! + v);
    }
    return sums;
  };

  const closest = (a: number[], need: number): number => {
    let lo = 0, hi = a.length - 1;
    while (lo < hi) {
      const mid = (lo + hi + 1) >> 1;
      if (a[mid]! <= need) lo = mid;
      else hi = mid - 1;
    }
    let best = a[lo]!;
    if (lo + 1 < a.length && Math.abs(a[lo + 1]! - need) < Math.abs(best - need)) {
      best = a[lo + 1]!;
    }
    return best;
  };

  const leftSums = allSums(left).sort((a, b) => a - b);
  let ans = Math.abs(goal);
  for (const r of allSums(right)) {
    const ls = closest(leftSums, goal - r);
    const diff = Math.abs(ls + r - goal);
    if (diff < ans) ans = diff;
  }
  return ans;
}

export function minAbsDifference(nums: number[], goal: number): number {
  const mid = nums.length >> 1;
  const left = nums.slice(0, mid);
  const right = nums.slice(mid);

  const allSums = (arr: number[]): number[] => {
    const sums = [0];
    for (const v of arr) {
      const n = sums.length;
      for (let i = 0; i < n; i++) sums.push(sums[i]! + v);
    }
    return sums;
  };

  const closest = (a: number[], need: number): number => {
    let lo = 0, hi = a.length - 1;
    while (lo < hi) {
      const mid = (lo + hi + 1) >> 1;
      if (a[mid]! <= need) lo = mid;
      else hi = mid - 1;
    }
    let best = a[lo]!;
    if (lo + 1 < a.length && Math.abs(a[lo + 1]! - need) < Math.abs(best - need)) {
      best = a[lo + 1]!;
    }
    return best;
  };

  const leftSums = allSums(left).sort((a, b) => a - b);
  let ans = Math.abs(goal);
  for (const r of allSums(right)) {
    const ls = closest(leftSums, goal - r);
    const diff = Math.abs(ls + r - goal);
    if (diff < ans) ans = diff;
  }
  return ans;
}

Şablon bağlantısı

Kanonik en-yakın-alt-küme-toplamı MITM — kalıp şablonu, açık lo / lo+1 en-yakın kontrolüyle.

Yansıma

Diziyi ikiye böl. Her yarının alt küme toplamlarını sırala. Bir yarıda goal − toplama en yakın.
Boş alt küme 0. Hedef dizide varsa fark 0. Negatif toplamlar sıralı aramayı bozmaz.
Cevap mutlak fark. n yaklaşık 40. Her yarı 2^(n/2). Tek eleman |a − goal|.