算法篇 ｜ 双指针

前言

在前端面试中，算法题是绕不开的一关。而在所有算法技巧中，双指针可以说是性价比最高的一个——它原理简单、适用范围广、面试出现频率极高。

双指针的核心思想就一句话：用两个指针在数据结构上同时移动，通过指针的相对位置和移动策略来减少不必要的遍历。 它能把很多看似需要 O(n²) 暴力枚举的问题，优化到 O(n) 的时间复杂度。

双指针并不是一个单一的技巧，而是一类策略的统称。根据两个指针的移动方式，可以分为三大类：

• 左右指针（对撞指针）：两个指针从数组两端向中间靠拢
• 快慢指针：两个指针从同一端出发，但速度不同
• 滑动窗口：本质也是双指针，但因为足够重要，我们在下一章单独讲

本章我们就把前两类——左右指针和快慢指针——彻底讲清楚，并通过经典 LeetCode 题目帮你建立肌肉记忆。

诊断自测

在开始正文之前，先试试下面这几道题，测测你目前对双指针的掌握程度。

Q1：给定一个升序数组和一个目标值，找出数组中两个数使它们的和等于目标值。要求 O(n) 时间复杂度，不能用哈希表。你会怎么做？

Q2：如何判断一个链表是否有环？要求 O(1) 空间复杂度。

Q3：给定一个有序数组，原地删除重复项，使每个元素只出现一次，返回新长度。要求 O(1) 额外空间。

一、左右指针（对撞指针）

左右指针是最直观的双指针形态：一个指针从左端开始，一个从右端开始，两者相向而行，直到相遇。

它适用的场景通常有一个共同特征：数据是有序的（或者可以利用某种单调性）。因为有序性保证了指针移动的方向是确定的——如果当前值太大就缩右边界，太小就扩左边界。

1.1 对撞指针模板

function twoPointerTemplate(arr) {
  let left = 0;
  let right = arr.length - 1;

  while (left < right) {
    // 根据条件判断移动哪个指针
    if (满足某个条件) {
      // 收集结果或处理逻辑
    } else if (需要扩大) {
      left++;
    } else {
      right--;
    }
  }
}

关键点：

1. 循环条件一般是 left < right（不取等号，因为两个指针指向同一个元素时没有意义）
2. 每次循环至少移动一个指针，保证不会死循环
3. 移动方向由问题的单调性决定

1.2 经典题：两数之和 II（LeetCode 167）

给定一个已排序的数组 numbers 和一个目标值 target，找出两个数的下标（1-indexed），使它们的和等于 target。

这是对撞指针最经典的应用场景。

思路：左指针指向最小值，右指针指向最大值。两者之和如果太大，说明需要减小，那就右指针左移；如果太小，就左指针右移。

function twoSum(numbers, target) {
  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]; // 题目保证有解，实际不会走到这里
}

为什么这是对的？ 因为数组是有序的，当 sum > target 时，如果不减小右边的值，无论左指针怎么右移，和只会更大。所以右指针左移是安全的——我们不会错过答案。同理，sum < target 时左指针右移也是安全的。

复杂度分析：

• 时间复杂度：O(n)，每个元素最多被访问一次
• 空间复杂度：O(1)，只用了两个指针变量

1.3 经典题：盛最多水的容器（LeetCode 11）

给定 n 个非负整数 height，每个整数代表一条垂直线段。找出两条线段，使它们与 x 轴构成的容器能容纳最多的水。

这道题乍一看和”两数之和”没什么关系，但它的核心逻辑同样是对撞指针。

关键洞察：容器的水量 = min(height[left], height[right]) * (right - left)。如果我们移动较高的那个指针，宽度减小了，而高度最多不变（取决于较矮的那根），所以水量一定减小。因此，每次移动较矮的那个指针，才有可能找到更大的容量。

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

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

    // 移动较矮的那一侧
    if (height[left] < height[right]) {
      left++;
    } else {
      right--;
    }
  }

  return maxWater;
}

复杂度分析：

• 时间复杂度：O(n)
• 空间复杂度：O(1)

面试追问：为什么移动较矮的指针是正确的？

答：假设 height[left] < height[right]，当前水量受限于 height[left]。如果移动右指针（较高的一侧），宽度减小 1，而新的高度 min(height[left], height[right-1]) 最多等于 height[left]（因为 min 的上界不变），所以水量一定不会增大。因此移动右指针不可能得到更优解，可以安全跳过。

二、快慢指针

快慢指针的特征是：两个指针从同一个位置出发，但移动速度不同。 最经典的用法是一个每次走一步（慢指针），另一个每次走两步（快指针）。

它主要用于两类问题：

1. 链表中的环检测（Floyd 判圈算法）
2. 数组/链表的原地操作（去重、移除元素等）

2.1 经典题：环形链表（LeetCode 141）

给定一个链表的头节点 head，判断链表中是否有环。

这是快慢指针最经典的应用——Floyd 判圈算法。

直觉：想象两个人在操场上跑步，一个跑得快，一个跑得慢。如果操场是环形的，快的人迟早会追上慢的人（套圈）。如果操场是直线的，快的人会先到终点。

function hasCycle(head) {
  let slow = head;
  let fast = head;

  while (fast !== null && fast.next !== null) {
    slow = slow.next;       // 慢指针走一步
    fast = fast.next.next;  // 快指针走两步

    if (slow === fast) {
      return true; // 相遇了，说明有环
    }
  }

  return false; // fast 到达了末尾，说明无环
}

为什么快指针每次走两步一定能追上慢指针？

假设慢指针进入环后，快指针在环中距离慢指针 k 步。每次循环，快指针比慢指针多走 1 步，所以距离每次缩小 1。经过 k 次循环后，距离变为 0，两者相遇。所以只要有环，一定会在环内相遇。

复杂度分析：

• 时间复杂度：O(n)
• 空间复杂度：O(1)

2.2 进阶：环形链表 II — 找到环的入口（LeetCode 142）

给定一个链表，返回链表开始入环的第一个节点。如果链表无环，返回 null。

这道题在面试中经常作为环形链表的追问出现。

核心推导：设链表头到环入口的距离为 a，环入口到相遇点的距离为 b，相遇点再走回环入口的距离为 c。那么：

• 慢指针走了 a + b 步
• 快指针走了 a + b + n(b + c) 步（n 为快指针在环中转的圈数）
• 因为快指针速度是慢指针的两倍：2(a + b) = a + b + n(b + c)
• 化简得：a = (n - 1)(b + c) + c

这意味着：从头节点走 a 步到环入口，等价于从相遇点走 c + (n-1) 圈到环入口。所以让一个指针从头节点出发，另一个从相遇点出发，都每次走一步，它们会在环入口相遇。

function detectCycle(head) {
  let slow = head;
  let fast = head;

  // 第一步：判断是否有环，找到相遇点
  while (fast !== null && fast.next !== null) {
    slow = slow.next;
    fast = fast.next.next;

    if (slow === fast) {
      // 第二步：找环的入口
      let ptr = head;
      while (ptr !== slow) {
        ptr = ptr.next;
        slow = slow.next;
      }
      return ptr;
    }
  }

  return null;
}

复杂度分析：

• 时间复杂度：O(n)
• 空间复杂度：O(1)

2.3 经典题：删除有序数组中的重复项（LeetCode 26）

给定一个升序数组 nums，原地删除重复项，使每个元素只出现一次，返回新长度。

思路：慢指针 slow 维护去重后的数组边界，快指针 fast 遍历原数组。当遇到一个新值时（nums[fast] !== nums[slow]），把它放到慢指针的下一个位置。

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; // 长度 = 最后一个位置的下标 + 1
}

复杂度分析：

• 时间复杂度：O(n)
• 空间复杂度：O(1)

这道题的快慢指针和链表环检测的快慢指针有什么不同？

链表环检测中，快指针”快”在每次走两步；而这里的快指针”快”在它遍历所有元素，而慢指针只在需要时才移动。本质上，慢指针维护的是”已处理结果”的边界，快指针负责探索。

三、双指针的通用思考框架

当你遇到一道新题时，如何判断能不能用双指针？这里给一个通用的判断思路：

1. 是否涉及”一对”元素的关系？（两数之和、容器两端）→ 考虑左右指针
2. 数据是否有序或单调？ → 有序性是左右指针的前提
3. 是否需要原地操作（O(1) 空间）？ → 考虑快慢指针
4. 是否涉及链表的环或位置关系？ → 考虑快慢指针
5. 是否涉及连续子序列？ → 考虑滑动窗口（下一章）

记住：双指针的本质是通过维护两个位置信息，避免重复遍历，从而将 O(n²) 优化到 O(n)。

常见误区

误区一：“双指针只能用在有序数组上”

左右指针确实要求某种单调性，但快慢指针不需要。链表环检测、数组去重都不要求全局有序。另外，即使数组无序，有时候可以先排序再用双指针（如三数之和），排序的 O(n log n) 通常是可以接受的。

误区二：“快慢指针只能用在链表上”

快慢指针在数组中同样大量使用。比如删除有序数组的重复项、移除元素（LeetCode 27）、移动零（LeetCode 283）等。只要是需要”原地修改，保持相对顺序”的场景，快慢指针都是首选。

误区三：“左右指针只要 left < right 就行了”

虽然大多数情况下循环条件是 left < right，但有些题目需要 left <= right（比如二分查找中的某些变种）。一定要根据具体问题分析：当 left === right 时，是否还有需要处理的情况。

误区四：“双指针题只需要写出答案，不用分析正确性”

面试中，面试官经常会追问”为什么移动这个指针是安全的”或者”为什么不会错过答案”。如果你只是背了模板但说不清原理，分数会大打折扣。每道双指针题，都要能解释清楚为什么指针的移动方向是对的。

小结

本章我们系统地讲解了双指针技巧的两大类型：

1. 左右指针（对撞指针）：从两端向中间逼近，利用有序性或单调性确定移动方向。经典场景包括两数之和、盛水容器、回文判断等。

2. 快慢指针：从同一端出发但速度不同，用于链表环检测（Floyd 算法）和数组原地操作（去重、移除元素等）。

双指针的核心价值在于：通过维护两个位置信息，将 O(n²) 的暴力搜索优化到 O(n)。 它不是一个复杂的算法，而是一种思维方式——当你看到一道需要在序列中找”一对”元素或做”原地操作”的题时，第一反应就应该想到双指针。

本章思维导图

练习挑战

第一题 ⭐：移动零（LeetCode 283）

给定一个数组 nums，将所有 0 移动到数组末尾，同时保持非零元素的相对顺序。要求原地操作。

// 示例
// 输入: [0, 1, 0, 3, 12]
// 输出: [1, 3, 12, 0, 0]

function moveZeroes(nums) {
  let slow = 0;

  // 快指针遍历数组，遇到非零就放到 slow 的位置
  for (let fast = 0; fast < nums.length; fast++) {
    if (nums[fast] !== 0) {
      // 交换 slow 和 fast 位置的元素
      [nums[slow], nums[fast]] = [nums[fast], nums[slow]];
      slow++;
    }
  }

  return nums;
}

第二题 ⭐⭐：三数之和（LeetCode 15）

给定一个数组 nums，找出所有和为 0 的三元组，不能包含重复的三元组。

// 示例
// 输入: [-1, 0, 1, 2, -1, -4]
// 输出: [[-1, -1, 2], [-1, 0, 1]]

function threeSum(nums) {
  const result = [];
  nums.sort((a, b) => a - b); // 先排序

  for (let i = 0; i < nums.length - 2; i++) {
    // 跳过重复的第一个数
    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]]);
        // 跳过重复的第二个数和第三个数
        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;
}

第三题 ⭐⭐⭐：接雨水（LeetCode 42）

给定 n 个非负整数表示柱子的高度，计算下雨后能接多少雨水。

// 示例
// 输入: [0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1]
// 输出: 6

function trap(height) {
  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]) {
      // 左边较矮，水量由左边最大值决定
      if (height[left] >= leftMax) {
        leftMax = height[left];
      } else {
        water += leftMax - height[left];
      }
      left++;
    } else {
      // 右边较矮，水量由右边最大值决定
      if (height[right] >= rightMax) {
        rightMax = height[right];
      } else {
        water += rightMax - height[right];
      }
      right--;
    }
  }

  return water;
}

自我检测

• 能说清楚左右指针和快慢指针的适用场景区别
• 能默写对撞指针模板，并解释循环条件为什么是 left < right
• 能用对撞指针解决两数之和 II，并解释为什么每次移动指针不会错过答案
• 能解释盛最多水的容器中”移动较矮指针”的贪心策略为什么是正确的
• 能用快慢指针实现链表环检测，并推导出环入口的数学证明
• 能用快慢指针原地删除有序数组的重复项
• 遇到新题时，能快速判断是否适合用双指针，以及该用哪种类型
• 能解释双指针技巧的本质——通过维护两个位置信息将 O(n²) 优化到 O(n)