雙指標技巧 — 四種模式完整解析與面試實戰 | 資料結構與演算法

// 已排序的陣列中找兩數之和等於 target，返回 1-indexed 位置
function twoSum(numbers: number[], target: number): number[] {
  let left = 0;
  let right = numbers.length - 1;

  while (left < right) {
    const sum = numbers[left] + numbers[right];

    if (sum === target) {
      return [left + 1, right + 1]; // 題目要求 1-indexed
    } else if (sum < target) {
      left++;  // 總和太小，左指標右移增大
    } else {
      right--; // 總和太大，右指標左移縮小
    }
  }

  return [-1, -1]; // 題目保證有解，不會到達這裡
}
// 時間：O(n)  空間：O(1)
// 前提：numbers 已排序（題目保證），對撞指標才能正確排除候選

function maxArea(height: number[]): number {
  let left = 0;
  let right = height.length - 1;
  let maxWater = 0;

  while (left < right) {
    const h = Math.min(height[left], height[right]);
    const w = right - left;
    maxWater = Math.max(maxWater, h * w);

    // 關鍵策略：移動較矮的那一側
    // 若移動較高側：寬度 -1，高度上界不變（受限於較矮側）→ 面積必定縮小
    // 若移動較矮側：寬度 -1，但高度上界可能提升 → 有機會找到更大面積
    if (height[left] <= height[right]) {
      left++;
    } else {
      right--;
    }
  }

  return maxWater;
}
// 時間：O(n)  空間：O(1)
// 正確性：對每對 (i, j)，可以證明被跳過的配對面積 ≤ 已計算的最大值

// 雙指標版（O(n) 時間，O(1) 空間）— 空間最優解
function trap(height: number[]): number {
  let left = 0;
  let right = height.length - 1;
  let leftMax = 0;
  let rightMax = 0;
  let water = 0;

  while (left < right) {
    if (height[left] < height[right]) {
      // 左側較矮：右側保證有 height[right] 以上的牆
      // 此格積水完全由 leftMax 決定（不受右側影響）
      leftMax = Math.max(leftMax, height[left]);
      water += leftMax - height[left]; // 若 height[left] 是新最大值，差為 0
      left++;
    } else {
      // 右側較矮：左側保證有 height[left] 以上的牆
      rightMax = Math.max(rightMax, height[right]);
      water += rightMax - height[right];
      right--;
    }
  }

  return water;
}
// 時間：O(n)  空間：O(1)
// 關鍵洞察：當 height[left] < height[right] 時，
// right 保證 rightMax >= height[right] > height[left]，
// 所以 left 的積水量完全由 leftMax 獨立決定。

function removeDuplicates(nums: number[]): number {
  // writePos 從 1 開始：位置 0 已確定保留（第一個元素無重複可比）
  let writePos = 1;

  for (let read = 1; read < nums.length; read++) {
    // 不等於前一個元素，說明是新的唯一值
    if (nums[read] !== nums[read - 1]) {
      nums[writePos++] = nums[read]; // 寫入並移動寫指標
    }
    // 若等於前一個，跳過（read 自動在 for 迴圈遞增）
  }

  return writePos; // 有效元素數量
}
// 時間：O(n)  空間：O(1)
// 不變量：nums[0..writePos-1] 始終是已確認的唯一元素序列

// 將陣列中所有 0 移到末尾，保持非零元素的相對順序
function moveZeroes(nums: number[]): void {
  let writePos = 0; // 下一個非零元素的寫入位置

  // 第一步：將所有非零元素依序移到前面
  for (let read = 0; read < nums.length; read++) {
    if (nums[read] !== 0) {
      nums[writePos++] = nums[read];
    }
  }

  // 第二步：剩餘位置補零
  while (writePos < nums.length) {
    nums[writePos++] = 0;
  }
}
// 時間：O(n)  空間：O(1)
// 範例：[0,1,0,3,12] → [1,3,12,0,0]
// 讀指標掃描全部，寫指標只在遇到非零時前進

class ListNode {
  val: number;
  next: ListNode | null;
  constructor(val: number, next: ListNode | null = null) {
    this.val = val;
    this.next = next;
  }
}

function detectCycle(head: ListNode | null): ListNode | null {
  if (!head || !head.next) return null;

  // 階段一：確認是否有環（龜兔賽跑）
  let slow: ListNode | null = head;
  let fast: ListNode | null = head;

  while (fast !== null && fast.next !== null) {
    slow = slow!.next;          // 慢指標走 1 步
    fast = fast.next.next;      // 快指標走 2 步

    if (slow === fast) {
      // 階段二：找環入口
      // 根據 Floyd 數學原理：a = k*c - b
      // head 到環入口的距離 = 相遇點到環入口的距離（沿環方向）
      let entry: ListNode | null = head;
      while (entry !== slow) {
        entry = entry!.next;
        slow = slow!.next;
      }
      return entry; // 即環入口節點
    }
  }

  return null; // 無環
}
// 時間：O(n)  空間：O(1)
// 相較於 HashSet 方案（O(n) 空間），快慢指標以 O(1) 空間解決問題

// fast 到達尾端時，slow 恰好在中間
// 偶數個節點時，返回第二個中間節點（偏右）
function middleNode(head: ListNode | null): ListNode | null {
  let slow: ListNode | null = head;
  let fast: ListNode | null = head;

  while (fast !== null && fast.next !== null) {
    slow = slow!.next;       // 走 1 步
    fast = fast.next.next;   // 走 2 步
  }

  return slow; // fast 到末尾，slow 恰在中間
}
// 時間：O(n)  空間：O(1)
// 奇數個節點（如 1→2→3→4→5）：slow 停在 3（正中）
// 偶數個節點（如 1→2→3→4）：  slow 停在 3（偏右中點）

// nums1 有 m 個有效元素，後面 n 個空位；nums2 有 n 個元素
function merge(nums1: number[], m: number, nums2: number[], n: number): void {
  let p1 = m - 1;        // nums1 有效元素末尾
  let p2 = n - 1;        // nums2 末尾
  let write = m + n - 1; // 寫入位置（從後往前）

  // 從大到小填入：比較兩個序列末尾，較大者放入 write 位置
  while (p1 >= 0 && p2 >= 0) {
    if (nums1[p1] >= nums2[p2]) {
      nums1[write--] = nums1[p1--];
    } else {
      nums1[write--] = nums2[p2--];
    }
  }

  // nums2 若有剩餘，直接填入（nums1 剩餘已在正確位置）
  while (p2 >= 0) {
    nums1[write--] = nums2[p2--];
  }
}
// 時間：O(m+n)  空間：O(1)
// 關鍵：write 指標永遠在 p1 右側，從後往前不會覆蓋未處理元素
// 範例：nums1=[1,2,3,0,0,0], m=3, nums2=[2,5,6], n=3
//       → nums1=[1,2,2,3,5,6]

#include <vector>
#include <algorithm>
using namespace std;

class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        vector<vector<int>> result;
        sort(nums.begin(), nums.end()); // 排序是對撞指標的前提

        for (int i = 0; i < (int)nums.size() - 2; i++) {
            if (nums[i] > 0) break;                        // 剪枝：最小值 > 0，無解
            if (i > 0 && nums[i] == nums[i-1]) continue;  // 去重：跳過重複的固定值

            int left = i + 1, right = (int)nums.size() - 1;

            while (left < right) {
                int sum = nums[i] + nums[left] + nums[right];

                if (sum == 0) {
                    result.push_back({nums[i], nums[left], nums[right]});
                    // upper_bound / lower_bound 利用有序性快速跳過重複值
                    auto nextLeft  = upper_bound(nums.begin() + left,
                                                 nums.begin() + right, nums[left]);
                    auto nextRight = lower_bound(nums.begin() + left + 1,
                                                 nums.begin() + right, nums[right]);
                    left  = (int)(nextLeft  - nums.begin());
                    right = (int)(nextRight - nums.begin()) - 1;
                } else if (sum < 0) {
                    left++;
                } else {
                    right--;
                }
            }
        }
        return result;
    }
};
// 時間：O(n²)  空間：O(1)（不計結果）

struct ListNode {
    int val;
    ListNode* next;
    explicit ListNode(int x) : val(x), next(nullptr) {}
};

class Solution {
public:
    ListNode* detectCycle(ListNode* head) {
        if (!head || !head->next) return nullptr;

        ListNode* slow = head;
        ListNode* fast = head;

        // 階段一：找相遇點
        while (fast != nullptr && fast->next != nullptr) {
            slow = slow->next;
            fast = fast->next->next;

            if (slow == fast) {
                // 階段二：找環入口
                ListNode* entry = head;
                while (entry != slow) {
                    entry = entry->next;
                    slow  = slow->next;
                }
                return entry;
            }
        }
        return nullptr; // 無環
    }
};

#include <vector>
#include <algorithm>
using namespace std;

// 雙序列指標的泛型版（與 std::merge 等價，此為教學示範）
template<typename InputIt1, typename InputIt2, typename OutputIt>
OutputIt mergeSorted(InputIt1 first1, InputIt1 last1,
                     InputIt2 first2, InputIt2 last2,
                     OutputIt out) {
    while (first1 != last1 && first2 != last2) {
        if (*first1 <= *first2) {
            *out++ = *first1++;
        } else {
            *out++ = *first2++;
        }
    }
    out = copy(first1, last1, out); // 剩餘部分直接複製
    out = copy(first2, last2, out);
    return out;
}
// 實際開發中直接用 std::merge，此為演示底層邏輯

function threeSum(nums: number[]): number[][] {
  const result: number[][] = [];
  nums.sort((a, b) => a - b); // 排序是對撞指標的前提

  for (let i = 0; i < nums.length - 2; i++) {
    // 剪枝：nums[i] > 0 表示三數之和必然 > 0，可直接結束
    if (nums[i] > 0) break;
    // 去重：i > 0 才能比前一個，相同值跳過避免重複三元組
    if (i > 0 && nums[i] === nums[i - 1]) continue;

    let left = i + 1;
    let right = nums.length - 1;

    while (left < right) {
      const sum = nums[i] + nums[left] + nums[right];

      if (sum === 0) {
        result.push([nums[i], nums[left], nums[right]]);
        // 去重：跳過 left 和 right 位置的重複值（必須在移動前執行）
        while (left < right && nums[left] === nums[left + 1]) left++;
        while (left < right && nums[right] === nums[right - 1]) right--;
        left++;
        right--;
      } else if (sum < 0) {
        left++;  // 總和太小，左指標右移增大
      } else {
        right--; // 總和太大，右指標左移縮小
      }
    }
  }

  return result;
}
// 時間：O(n²)  空間：O(1)（不計結果空間）
// 常見錯誤：
//   1. 忘記排序
//   2. 找到答案後忘記去重，導致重複三元組
//   3. 去重時沒有確保 left < right 的邊界條件

function sortColors(nums: number[]): void {
  let low = 0;                    // [0, low) 全是 0
  let mid = 0;                    // [low, mid) 全是 1
  let high = nums.length - 1;     // (high, end] 全是 2

  while (mid <= high) {
    if (nums[mid] === 0) {
      // 當前是 0：與 low 交換，兩者都前進
      [nums[low], nums[mid]] = [nums[mid], nums[low]];
      low++;
      mid++;
    } else if (nums[mid] === 1) {
      // 當前是 1：已在正確區間，mid 前進
      mid++;
    } else {
      // 當前是 2：與 high 交換，high 後退，mid 不動（換來的值需再次檢查）
      [nums[mid], nums[high]] = [nums[high], nums[mid]];
      high--;
    }
  }
}
// 時間：O(n)  空間：O(1)
// 不變量（Invariant）：
//   nums[0..low-1]   全為 0
//   nums[low..mid-1] 全為 1
//   nums[mid..high]  未處理區間
//   nums[high+1..n-1] 全為 2

function removeNthFromEnd(head: ListNode | null, n: number): ListNode | null {
  const dummy = new ListNode(0);
  dummy.next = head;

  let fast: ListNode | null = dummy;
  let slow: ListNode | null = dummy;

  // fast 先走 n+1 步（+1 讓 slow 停在目標節點的前一個）
  for (let i = 0; i <= n; i++) {
    fast = fast!.next;
  }

  // 兩者同步前進直到 fast 到達末尾
  while (fast !== null) {
    fast = fast.next;
    slow = slow!.next;
  }

  // slow.next 就是要刪除的節點
  slow!.next = slow!.next!.next;
  return dummy.next;
}
// 時間：O(n)  空間：O(1)
// dummy 節點技巧：統一處理刪除頭節點的邊界情況

// 錯誤：陣列無序時對撞指標會跳過正確答案
// 反例：nums = [3, 1, 2], target = 4
// left=3, right=2: sum=5>4, right--
// left=3, right=1: sum=4，但正確答案 [1,3] 已被跳過！

// 正確：對撞指標前必須排序（若需原始索引，用 Map 記錄）
nums.sort((a, b) => a - b);

// 錯誤：找到答案後直接移動，未跳過重複值
if (sum === 0) {
  result.push([nums[i], nums[left], nums[right]]);
  left++;  // 若 nums[left+1] === nums[left]，下次會推入相同三元組
  right--;
}

// 正確：移動前先跳過所有重複值，且需確保 left < right
if (sum === 0) {
  result.push([nums[i], nums[left], nums[right]]);
  while (left < right && nums[left] === nums[left + 1]) left++;
  while (left < right && nums[right] === nums[right - 1]) right--;
  left++;
  right--;
}

// 錯誤：fast 從 head.next 開始，邊界行為不一致
let slow = head;
let fast = head.next; // 起始點不同，偶數個節點時中點偏左

// 正確：slow 和 fast 都從 head 出發
let slow: ListNode | null = head;
let fast: ListNode | null = head;
while (fast !== null && fast.next !== null) {
  slow = slow!.next;
  fast = fast.next.next;
}

// 錯誤：直接相減，未更新 leftMax 時可能得到負數
totalWater += leftMax - height[left]; // 若 height[left] > leftMax，結果為負！

// 正確：先更新 leftMax，再計算差值
leftMax = Math.max(leftMax, height[left]);
totalWater += leftMax - height[left]; // 若 height[left] 是新最大值，差值為 0（正確）