שני מצביעים וחלון גולש - הטכניקות הכי שכיחות בראיונות

Two Pointers ו-Sliding Window הן שתי טכניקות שמשפרות פתרונות נאיביים מ-O(n²) ל-O(n). הן מופיעות בעשרות שאלות ראיון נפוצות ב-LeetCode, Google, Meta ו-Amazon - וכדאי לזהות אותן מהר.

Two Pointers - שני מצביעים שזזים

ממקמים שני מצביעים (בדרך כלל בשתי קצוות המערך) והזזים אותם לקראת אחד השני על פי תנאי. עובד על מערכים ממוינים ובעיות סימטריות.

// בעיה: האם יש זוג שמסכם ל-target? (מערך ממוין)
function twoSum(arr, target) {
  let left = 0, right = arr.length - 1;
  while (left < right) {
    const sum = arr[left] + arr[right];
    if (sum === target) return [left, right];
    else if (sum < target) left++;
    else right--;
  }
  return null;
}
// O(n) זמן, O(1) זיכרון - במקום O(n²) נאיבי

דוגמאות נוספות ל-Two Pointers

• בדיקת Palindrome - שני מצביעים מהקצוות לפנים
• Container With Most Water - מזיזים את הצד הנמוך יותר
• Remove Duplicates from Sorted Array - מצביע כותב ומצביע קורא
• 3Sum - קיבוע איבר אחד + Two Pointers על השאר

Sliding Window - חלון גולש

Sliding Window מתאים לבעיות על subarray או substring רציפים. במקום לחשב כל תת-מערך מחדש, שומרים 'חלון' ומעדכנים רק את הקצוות שמשתנים.

חלון בגודל קבוע

// בעיה: סכום מקסימלי של תת-מערך באורך k
function maxSumSubarray(arr, k) {
  let sum = arr.slice(0, k).reduce((a, b) => a + b, 0);
  let max = sum;
  for (let i = k; i < arr.length; i++) {
    sum += arr[i] - arr[i - k]; // הוסף מימין, הסר משמאל
    max = Math.max(max, sum);
  }
  return max;
}
// O(n) במקום O(n·k) נאיבי

חלון בגודל משתנה

// בעיה: substring ארוכה ביותר ללא אותיות חוזרות
function lengthOfLongestSubstring(s) {
  const seen = new Map();
  let left = 0, max = 0;
  for (let right = 0; right < s.length; right++) {
    if (seen.has(s[right]) && seen.get(s[right]) >= left) {
      left = seen.get(s[right]) + 1; // כווץ חלון
    }
    seen.set(s[right], right);
    max = Math.max(max, right - left + 1);
  }
  return max;
}

איך לזהות את הטכניקה הנכונה?