双指针

“双指针”是一种常用的算法技巧，常用于数组、字符串等线性结构上，能够高效地解决许多查找、遍历、比较类的问题。顾名思义，就是使用两个指针（变量）来遍历数据结构，常见的方式包括：

🌟 常见双指针模式

1️⃣ 同向双指针（滑动窗口）

• 两个指针从头开始，一起向前移动，常用于 子数组/子串问题。

典型例子：

• 求最长不重复子串
• 子数组和为固定值（如 Leetcode 209 最短子数组长度）

// JS 示例：最长不重复子串长度
function lengthOfLongestSubstring(s) {
  let set = new Set();
  let left = 0, maxLen = 0;
  for (let right = 0; right < s.length; right++) {
    while (set.has(s[right])) {
      set.delete(s[left]);
      left++;
    }
    set.add(s[right]);
    maxLen = Math.max(maxLen, right - left + 1);
  }
  return maxLen;
}

2️⃣ 对撞指针（从两端向中间靠拢）

• 左右两个指针分别从两头向中间移动，常用于 排序数组中找某个组合 或 回文判断。

典型例子：

• 判断回文字符串
• 两数之和（有序数组）
• 三数之和

// JS 示例：有序数组中找两个数之和为 target
function twoSum(nums, target) {
  let left = 0, right = nums.length - 1;
  while (left < right) {
    const sum = nums[left] + nums[right];
    if (sum === target) return [left, right];
    else if (sum < target) left++;
    else right--;
  }
  return [];
}

3️⃣ 快慢指针

• 一个指针快，一个慢，常用于 链表操作，比如 寻找环、找到中点。

典型例子：

• 判断链表是否有环（Floyd 判圈算法）
• 删除链表倒数第 N 个节点

// JS 示例：判断链表是否有环
function hasCycle(head) {
  let slow = head, fast = head;
  while (fast && fast.next) {
    slow = slow.next;
    fast = fast.next.next;
    if (slow === fast) return true;
  }
  return false;
}

✅ 双指针常用场景总结：