双指针技巧

双指针技巧

两类双指针

“双指针”这个名字盖住了两种其实不太一样的东西：

  • 快慢指针 —— 两个指针同向走，速度不同。用于链表（环检测、找中点、找倒数第 k 个）和数组的原地修改。
  • 左右指针 —— 两个指针从两端向中间收，或从中间向两端扩。用于有序数组的查找、反转、回文判断。

⭐ 拿到题先判断是哪一类，剩下的就是套模板。判断依据很简单： 数据有序或者需要从两端看 → 左右指针；链表或者需要原地覆盖 → 快慢指针。

快慢指针：链表环检测

经典问题：判断一个单链表有没有环。

function hasCycle(head) {
  let slow = head, fast = head;
  while (fast !== null && fast.next !== null) {
    slow = slow.next;
    fast = fast.next.next;
    if (slow === fast) return true;
  }
  return false;
}

原理：如果有环，快指针每次比慢指针多走一步，两者的距离每轮缩小 1， 最终一定会相遇 —— 就像操场上跑得快的人一定会套圈跑得慢的人。 如果没环，快指针会先撞到 null。

⚠️ while 的条件必须同时判 fast 和 fast.next。只写 fast !== null 的话， 无环链表上会抛异常 —— 但只在奇数长度时抛。实测：

长度 1  ❌ TypeError      长度 2  false
长度 3  ❌ TypeError      长度 4  false
长度 5  ❌ TypeError      长度 6  false
长度 7  ❌ TypeError      长度 8  false

原因是 fast 每轮走两步，落点的奇偶性是固定的：

  • 偶数长度 → fast 恰好落在最后一个节点的 next（即 null）上， 循环条件 fast !== null 挡住，安全退出
  • 奇数长度 → fast 落在最后一个节点上，fast !== null 通过， 接着算 fast.next.next 时 fast.next 是 null → 抛错

n = 5 的逐轮追踪：

第 1 轮  fast 0→2, slow→1
第 2 轮  fast 2→4, slow→2
第 3 轮  fast=4, fast.next=null → 取 fast.next.next 抛 TypeError

🚨 所以测试用例的长度奇偶决定了你能不能发现这个 bug。 长度 1~10 逐个跑过，奇数五个全抛、偶数五个全部安全返回 false —— 长度均匀取的话正好一半的随机用例触发不了。

⚠️ 更麻烦的是这个 bug 只在无环链表上出现：有环时 fast 永远撞不到 null， 两个指针必定先相遇并 return true。 「长度 1~40 × 环起点取遍每个位置」共 820 种有环链表， 错法一次没抛错、答案也全对。

📌 所以两类用例它都躲得掉：有环的躲掉是必然，无环的躲掉靠长度是偶数。 要暴露它，必须专门喂一条奇数长度的无环链表 —— 单节点链表就够。

快慢指针：原地去重

有序数组原地去重，要求返回去重后的长度：

function removeDuplicates(nums) {
  if (nums.length === 0) return 0;
  let slow = 0;
  for (let fast = 1; fast < nums.length; fast++) {
    if (nums[fast] !== nums[slow]) {
      slow++;
      nums[slow] = nums[fast];
    }
  }
  return slow + 1;
}

慢指针维护“已经处理好的区间”的右边界，快指针负责往前探。 这个结构在“原地移除某些元素”这一类题里是通用的， 只要把 nums[fast] !== nums[slow] 换成对应的保留条件。

左右指针：反转数组

function reverse(nums) {
  let left = 0, right = nums.length - 1;
  while (left < right) {
    [nums[left], nums[right]] = [nums[right], nums[left]];
    left++;
    right--;
  }
}

📌 循环条件是 left < right 而不是 left <= right。 用 <= 时，长度为奇数的数组中间那个元素会和自己交换一次。实测交换次数：

长度 4（偶）   <  2 次    <=  2 次     结果相同
长度 5（奇）   <  2 次    <=  3 次     结果相同
长度 6（偶）   <  3 次    <=  3 次     结果相同
长度 7（奇）   <  3 次    <=  4 次     结果相同

⭐ 只有奇数长度多一次，且结果永远相同 —— 所以它不是 bug，只是一次浪费。 ⚠️ 但在某些变体题里（比如统计交换次数、或者交换时带副作用）会导致重复计数。

⭐ 左右指针的主场：对撞求和

反转数组只是热身。左右指针真正的用处，是在有序数组上把 O(n²) 的枚举压成 O(n)：

// 有序数组里找两个数，和为 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];
    if (sum < target) left++;      // 和小了 → 只能把小的那头往大走
    else right--;                  // 和大了 → 只能把大的那头往小走
  }
  return [-1, -1];
}

⭐ 为什么这样不会漏解：每次移动都排除掉一整排不可能的组合。 sum < target 时，nums[left] 和右边任何一个数配都不够大 —— left 这一整行都可以划掉，所以 left++ 是安全的。

📌 这个「每一步排除一整行」的论证，是所有左右指针题的正确性来源。 面试被追问「怎么保证不漏」，答这一句。

盛最多水的容器：同样的论证，换个量

题意复述：数组每个值是一根柱子的高度，选两根柱子和 x 轴围成容器，求最大盛水量。

function maxArea(height) {
  let left = 0, right = height.length - 1, best = 0;
  while (left < right) {
    best = Math.max(best, Math.min(height[left], height[right]) * (right - left));
    // 🚨 永远移动矮的那一边
    if (height[left] < height[right]) left++;
    else right--;
  }
  return best;
}

🚨 为什么必须移动矮的那边？ 面积 = 短板 × 宽度。移动高的那边， 宽度一定减小，而短板最多不变（还是原来那个矮的）—— 面积必然不增， 这一步白走。移动矮的那边，短板才有可能变高。

⚠️ 移反了不报错，只是答案偏小。[1,8,6,2,5,4,8,3,7] 上正确答案是 49 （暴力枚举验证过），一律移动高的那边会得到 8 —— 差 6 倍多。

随机高度数组实测（各 3000 组）。⚠️ 出错率取决于数组多长、值域多宽：

长度 2~12、值 0~19      错 59.1%        ← 正文这一行的参数
长度 2~12、值 0~4       错 59.9%
长度 5~30、值 0~99      错 83.1%
长度 10、  值 0~999     错 77.9%

四种设置下偏大的组数：0 / 0 / 0 / 0

⭐ 数组越长越容易错（可选的组合更多，跳过更优解的机会也更多）。 ⚠️ 但**「全部偏小、没有一个偏大」在所有设置下都成立** —— 10 万组大样本里有 66036 组答案不同，偏大的仍然是 0 个。

这一条是可推导的：移错方向只会让你跳过更优的组合， 不会凭空造出更大的面积。症状的方向本身就是定位线索。 ⚠️ 而在最短的那档里仍有四成用例照样对 —— 随手试两个短数组很可能都过。

怎么认出该用双指针

前面都在讲「怎么写」。实际做题时更难的是「什么时候想到它」。三条判据：

① 要找的是「一对」或「一段」，而暴力解法是两层循环。 双指针能省掉一层，前提是有办法排除掉一整片候选 —— 通常靠有序。

② 数组有序（或能排序而不影响答案）→ 优先想左右指针。 「有序」是那个「排除一整行」论证的前提。 ⚠️ 反过来：题目要求保持原下标时不能排序，那就换哈希表。

③ 要在链表上定位、或者要原地修改数组 → 快慢指针。 链表不能随机访问，「倒数第 k 个」「中点」只能靠两个指针拉开距离走出来。

与滑动窗口的分界

滑动窗口也是两个同向指针，容易和快慢指针混。 区别在于两个指针之间的那段有没有意义：

  • 快慢指针：slow 之前是「已处理好的区间」，中间那段是垃圾，没有意义
  • 滑动窗口：[left, right] 之间就是答案的候选，要一直维护它的状态

📌 一句话：要维护「窗口内的性质」就是滑窗，只是拿两个指针走位就是双指针。

左右指针：二分搜索也是双指针

二分本质上就是左右指针：

function binarySearch(nums, target) {
  let left = 0, right = nums.length - 1;
  while (left <= right) {
    const mid = left + Math.floor((right - left) / 2);
    if (nums[mid] === target) return mid;
    if (nums[mid] < target) left = mid + 1;
    else right = mid - 1;
  }
  return -1;
}

🚨 mid 要写成 left + (right - left) / 2 而不是 (left + right) / 2。 后者在 left 和 right 都很大时会整数溢出 —— Java / C++ 里这是一个真实存在过的 经典 bug（曾潜伏在 JDK 的 Arrays.binarySearch 里九年）。

⚖️ 但 JavaScript 里的症状和那个经典 bug 不是一回事，值得说清楚。实测两种写法：

left = 0,                 right = 10                  两者都得 5
left = 1e9,               right = 2e9                 两者都得 1500000000
left = 2⁵²,               right = 2⁵²+10              两者都得 4503599627370501
left = 2⁵³−10,            right = 2⁵³−1（MAX_SAFE）   两者都得 9007199254740986

JS 的 Number 是浮点，不会像定长整型那样溢出成负数 —— left + right 超过 2⁵³ 之后是丢精度。两种写法要到 2⁵³ 才第一次分岔：

left = 2⁵³, right = 2⁵³ + 3
  left + (right - left)/2  →  9007199254740992
  (left + right)/2         →  9007199254740994      差 2，都不是负数

数组下标不可能到 2⁵³，所以这个写法在 JS 里实际上碰不到问题。

👉 那还写不写？写。 理由不是「防 JS 溢出」，是换语言时不会栽。 把同一行放进 32 位整型语义里跑一遍，差别一目了然：

left = 2³⁰, right = 2³⁰ + 10          （都远小于 int 上限）
  (left + right) / 2      →  -1073741819     🚨 变成了负数
  left + (right-left)/2   →   1073741829     ✅ 正确

⭐ 2³⁰ + 2³⁰ 就已经越过 int 的 2³¹−1 上限翻成负数 —— 而 left 和 right 各自都只是十亿量级，看起来完全正常。 📌 把安全写法当成一个跨语言的书写习惯，而不是当成 JS 里必须防的坑。

二分的边界条件（<= 还是 <、mid + 1 还是 mid）单独一篇讲，见后续章节。

练习

勾选记录做过哪些，0 / 5 道。进度只存在这台设备的浏览器里；同一道题在别篇勾过，这里也会显示已做。

⚖️ 这里只给题号、官方标题和链接，不复述题面 —— 平台的题面文字有版权。 「这题考什么」写的是它对应本篇的哪个点，那部分是本站自己的内容。

在本站 OJ 上练

这几道题在自己搭的判题机上，注册后直接提交，几秒出结果 —— 不用装环境、不用自己造测试数据。题目是自出的（无版权问题），每道题的数据都要求能抓出典型错解才准上线， 所以「样例过了」不等于能过。