sko.kr

算法 - 3. 双指针（Two Pointers）

algorithmstwo-pointersarraysstringsoptimization
By sko•9/28/2025•15 min read

何时使用双指针

当你需要系统地探索不同位置元素之间的关系时使用双指针。当你可以根据某些条件移动指针来取得进展，同时消除可能性时，这种技术就能发挥作用。

需要排序数组的问题

  • 带目标的两数之和（经典用例 - 需要排序来知道移动哪个指针）
  • 三数之和 / 四数之和（使用嵌套指针对 - 需要顺序来消除）
  • 查找具有特定差值的对（需要顺序来消除区域）

在未排序数组上工作的问题

  • 盛最多水的容器（索引提供顺序，而非值）
  • 回文验证（从两端自然排序）
  • 反转数组/字符串（从两端交换）
  • 分区问题（荷兰国旗问题，快速排序分区）
  • 快慢指针变体（循环检测，查找中间元素）
  • 使用读写指针删除重复项（扫描时维护不变量）

示例问题（排序数组）

查找目标和的一对数字：给定排序整数数组 [1, 3, 4, 6, 8, 9, 11] 和目标和 14，找到两个相加等于目标的数字。

  • 从位置 0 和 6 的指针开始：1 + 11 = 12（太小）
  • 将左指针移到位置 1：3 + 11 = 14（找到了！）
  • 答案：索引 [1, 6] 处的元素，即 3 和 11

没有排序，你需要 O(n²) 次比较。在排序数组上使用双指针，你可以在 O(n) 时间内找到它。

示例问题（未排序数组）

盛最多水的容器：给定高度 [1, 8, 6, 2, 5, 4, 8, 3, 7]，找到两条线，它们与 x 轴一起形成一个容纳最多水的容器。

  • 从位置 0 和 8 的指针开始：面积 = 8 × min(1, 7) = 8
  • 移动左指针（较小高度）到位置 1：面积 = 7 × min(8, 7) = 49
  • 继续直到指针相遇，跟踪最大面积
  • 答案：索引 [1, 8]，面积 49

不需要排序！索引本身提供宽度，我们移动较小高度的指针以潜在地找到更大的面积。

最重要的洞察

双指针通过每次指针移动消除不可能的选项来系统地探索解空间 - 无论是通过排序顺序（对于求和问题）还是位置约束（对于几何问题），每次比较都给我们关于许多可能性的知识，而不仅仅是一个。

心理笔记：与专注于"在位置 i 结束的最佳子数组"的 Kadane 算法和滑动窗口不同，双指针专注于不同位置元素之间的关系。你不会锚定在任何位置 - 相反，你通过基于比较移动两个独立的指针来探索对/关系。当 Kadane 问"在这个位置扩展还是重新开始？"时，双指针问"应该移动哪个指针来找到更好的关系？"

心理模型比较

  • Kadane 算法："在位置 i 结束的最佳子数组是什么？" - 锚定到端点
  • 滑动窗口："在位置 i 结束的最佳窗口是什么？" - 锚定到右边界
  • 双指针："接下来应该探索两个位置之间的什么关系？" - 无锚点，纯粹探索

缺少位置锚定使双指针独特 - 你可以根据比较自由移动任一指针，系统地消除解空间的整个区域。

决策框架

对于排序数组问题（两数之和）

  • 和太大？将右指针向左移动（减少和）
  • 和太小？将左指针向右移动（增加和）
  • 和等于目标？找到配对！

对于未排序数组问题（盛最多水的容器）

  • 移动指向较小高度的指针
  • 为什么？较小的高度限制了面积，所以我们寻找潜在更高的线
  • 跟踪到目前为止看到的最大面积

代码示例

排序数组：两数之和

function twoSum(nums: number[], target: number): [number, number] | null {
  let left = 0;
  let right = nums.length - 1;

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

    // DECISION FRAMEWORK
    if (currentSum > target) {
      // 和太大：将右指针向左移动来减少
      right--;
    } else if (currentSum < target) {
      // 和太小：将左指针向右移动来增加
      left++;
    } else {
      // 找到目标和
      return [left, right];
    }
  }

  return null; // 未找到有效配对
}

// 使用问题中的数据的示例
const sortedArray = [1, 3, 4, 6, 8, 9, 11];
const targetSum = 14;
const result = twoSum(sortedArray, targetSum);
console.log(result); // [1, 6] - 3 和 11 的索引

未排序数组：盛最多水的容器

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

  while (left < right) {
    const width = right - left;
    const minHeight = Math.min(heights[left], heights[right]);
    const currentWater = width * minHeight;

    maxWater = Math.max(maxWater, currentWater);

    // DECISION FRAMEWORK
    if (heights[left] < heights[right]) {
      // 左墙是限制因素，尝试找到更高的左墙
      left++;
    } else {
      // 右墙是限制因素，尝试找到更高的右墙
      right--;
    }
  }

  return maxWater;
}

// 使用问题中未排序数组的示例
const heights = [1, 8, 6, 2, 5, 4, 8, 3, 7];
console.log(maxArea(heights)); // 49（索引 1 和 8 之间）

未排序数组：回文检查

function isPalindrome(s: string): boolean {
  let left = 0;
  let right = s.length - 1;

  while (left < right) {
    // DECISION FRAMEWORK
    if (s[left] !== s[right]) {
      return false; // 发现不匹配
    }
    left++;
    right--;
  }

  return true; // 所有字符都匹配
}

// 适用于任何字符串 - 不需要排序！
console.log(isPalindrome("racecar")); // true
console.log(isPalindrome("hello")); // false

超越排序数组：双指针仍然有效的情况

常见误解："双指针只适用于排序数组。"

这是错误的！双指针在以下情况下有效：

  1. 通过基于条件移动指针来进行系统性进展
  2. 消除可能性或系统地探索解空间
  3. 通过使用某种结构（不一定是排序顺序）来避免冗余比较

为什么盛最多水的容器在未排序数组上有效

关键洞察：索引本身提供了我们需要的顺序！

  • 宽度始终是 right - left（随着指针收敛而减少）
  • 我们移动较小高度的指针，因为它是限制因素
  • 每次移动都探索具有较小宽度但潜在更大高度的容器
  • 不需要排序，因为位置（而非值）决定宽度

不同的结构使双指针成为可能

  1. 排序值 → 为和/差问题启用方向性决策
  2. 位置索引 → 为几何问题提供自然排序
  3. 字符串/数组末端 → 回文/反转问题的自然边界
  4. 不变量维护 → 用于就地修改的读/写指针

"结构"不一定是排序值 - 它只需要能够实现系统性探索！

疑虑消除（排序数组情况）

常见疑虑："算法基于与目标的比较来移动指针，但如果我们跳过了正确的配对怎么办？一旦我们越过一个元素，就再也不会回去 - 这难道不会错过解决方案吗？"

为什么这种想法是错误的

关键认识：每次指针移动都消除了整个不可能配对的类别！

  • 当和 < 目标时 → 将左指针向右移动 → 消除当前左元素的所有配对（它们都太小）
  • 当和 > 目标时 → 将右指针向左移动 → 消除当前右元素的所有配对（它们都太大）

系统性探索的实际操作

让我们跟踪目标为 7 的 [1, 3, 4, 6, 8]：

步骤 1：left=0 (1), right=4 (8) → sum=9 > 7
        消除：8 与元素≥1 的所有配对
        将 right 移到 3

步骤 2：left=0 (1), right=3 (6) → sum=7 = 7  → 找到了！

注意步骤 1 发生了什么：

  • 我们比较了 1+8=9 与目标 7
  • 因为 9 > 7，我们知道 8 与 1、3、4 或 6 配对都会 ≥ 9
  • 所以我们可以安全地完全排除 8

为什么方向性移动保证完整性

算法维护这个不变量：

  • 我们已经通过的左元素的所有配对都已完全探索
  • 我们已经通过的右元素的所有配对都已完全探索
  • 剩余的未探索空间系统地缩小直到为空

保证：因为排序顺序让我们知道基于单次比较哪些整个区域是不可能的，我们可以在每次指针移动时消除许多配对。这种系统性探索确保我们精确地检查每个可行的配对一次，同时跳过所有不可能的配对！

魔力在于排序数组：它将与一对的比较转化为关于许多对的知识，让我们在 O(n) 时间而不是 O(n²) 时间内探索整个解空间。

疑虑消除（未排序数组情况）

常见疑虑："双指针如何在未排序数组上工作？难道我们不需要排序来知道移动哪个指针吗？"

为什么这种想法是错误的

关键认识：排序只是创建结构的一种方式。只要有任何可利用的结构，双指针就能工作！

对于未排序数组，结构来自：

  • 位置关系（盛最多水的容器：索引决定宽度）
  • 自然边界（回文：从两端向内比较）
  • 维护的不变量（分区：指针前的元素满足条件）

盛最多水的容器 - 为什么不需要排序

考虑高度 [1, 8, 6, 2, 5, 4, 8, 3, 7]。算法之所以有效是因为：

  1. 宽度由索引决定，而非值：位置 i 和 j 之间的距离始终是 |i - j|
  2. 移动指针始终减少宽度：这由索引位置保证
  3. 我们移动较短的线，希望找到更高的线：由于宽度减少，只有更高的线才能提供更大的面积

关键洞察：索引本身提供了我们需要的顺序。我们不是通过比较值来找配对 - 我们使用的是无论值顺序如何都存在的位置关系。

为什么排序实际上会破坏某些问题

对于盛最多水的容器，排序会破坏位置关系：

  • 原始：[1, 8, 6, 2, 5, 4, 8, 3, 7] - 索引很重要
  • 排序：[1, 2, 3, 4, 5, 6, 7, 8, 8] - 失去了原始位置！

问题依赖于元素的原始位置，而不是它们的排序顺序。

记住：双指针需要结构，不一定是排序值。识别什么结构能在你的特定问题中实现系统性探索。

变体和模式

快慢指针（龟兔赛跑）

指针以不同速度移动的特殊变体：

function hasCycle(head: ListNode | null): boolean {
  let slow = head;
  let fast = head;

  while (fast && fast.next) {
    slow = slow.next; // 移动 1 步
    fast = fast.next.next; // 移动 2 步

    // DECISION FRAMEWORK
    if (slow === fast) {
      return true; // 检测到循环
    }
  }

  return false; // 没有循环
}

用于就地修改的读/写指针

这种模式使用两个以不同速度在同一方向移动的指针来就地修改数组：

function removeDuplicates(nums: number[]): number {
  if (nums.length === 0) return 0;

  let writePointer = 0; // 写入下一个唯一元素的位置

  for (let readPointer = 1; readPointer < nums.length; readPointer++) {
    // DECISION FRAMEWORK
    if (nums[readPointer] !== nums[writePointer]) {
      writePointer++;
      nums[writePointer] = nums[readPointer];
    }
  }

  return writePointer + 1; // 唯一元素的长度
}

// 示例：[1,1,2,2,3] 变成 [1,2,3,2,3]，长度为 3

工作原理：

  • 读指针扫描整个数组寻找新的唯一值
  • 写指针标记下一个唯一值应该写入的位置
  • 当读指针找到与写指针处的值不同的值时：
    1. 向前移动写指针
    2. 将新的唯一值复制到写入位置
  • 数组被就地修改：[1,1,2,2,3] → [1,2,3,2,3]
    • 前 3 个元素现在是唯一值：[1,2,3]
    • 剩余元素 [2,3] 被忽略（它们超出了我们的新长度）
  • 返回 3，表示前 3 个元素包含所有唯一值

这种模式对于想要保留某些元素同时删除其他元素的就地数组修改非常强大，全部在 O(n) 时间和 O(1) 空间内完成。

← Back to Blog