精通编码面试：第2部分（双指针模式）
Source: Dev.to
如果你已经阅读了本系列的第 1 部分，就会知道单一的模式如何把慢速、暴力的解法转变为优雅且高效的方案。今天我们将做同样的事——但换上一件新工具：双指针模式。
这种模式在编码面试中随处可见。一旦你认出它，就会在以前可能让你苦恼的问题中频频看到它。
什么是双指针模式？
思路很简单：与其使用一个索引遍历数据结构，不如使用 两个。这两个指针根据特定条件在数组（或字符串）中移动，协同帮助你在不需要嵌套循环的情况下找到答案。
| 变体 | 描述 |
|---|---|
| 相反方向指针 | 一个指针从开头开始，另一个从末尾开始。它们向彼此移动，直至相遇。 |
| 同方向指针（快慢指针） | 两个指针从同一端开始，但以不同速度或在不同条件下移动。 |
让我们直接进入一个问题，看看第一种变体的实际应用。
Source: …
问题 1 — 两数之和 II：输入数组已排序
给定一个 从 1 开始索引 的整数数组 numbers，该数组已按非递减顺序排序，找出两个数使它们的和等于特定的 target 值。返回这两个数的索引，形式为长度为 2 的整数数组 [index1, index2]。
暴力解法
class Solution:
def twoSum(self, numbers: List[int], target: int) -> List[int]:
for i in range(len(numbers)):
for j in range(i + 1, len(numbers)):
if numbers[i] + numbers[j] == target:
return [i + 1, j + 1] # 1‑indexed result
return []时间复杂度：O(n²) – 对于 30 000 个元素的数组，这相当于 9 亿次比较。
结果：在大规模输入（LeetCode）上 超出时间限制。在实际生产环境中，对大数据集进行二次循环是性能瓶颈。
使用双指针模式的优化
我们在暴力方法中忽略的关键点是 数组已经排好序。这个提示让我们可以使用双指针模式：
- 将一个指针放在开头（
left），另一个放在末尾（right）。 - 计算它们的和。
- 若和 等于 目标 → 返回索引。
- 若和 过大 → 将
right向左移动，以获得更小的值。 - 若和 过小 → 将
left向右移动，以获得更大的值。
每一次迭代都会剔除一个候选，由于指针会相互逼近，我们能够在一次遍历中找到答案（或确认不存在）。
class Solution:
def twoSum(self, numbers: List[int], target: int) -> List[int]:
left = 0 # start of the array
right = len(numbers) - 1 # end of the array
while left < right:
current_sum = numbers[left] + numbers[right]
if current_sum == target:
# Return 1‑indexed result
return [left + 1, right + 1]
if current_sum > target:
# sum too large → move right pointer left
right -= 1
else:
# sum too small → move left pointer right
left += 1
return [] # problem guarantees a solution, but good practice时间复杂度：O(n)
空间复杂度：O(1)
相比暴力解法，这是一项显著的改进，并且在 LeetCode 上能够顺利通过。
变体 2 — 同向指针
第二种变体并不是从相对两端收敛。相反，两个指针从同一侧开始，并 朝相同方向 移动，但速度不同或在不同条件下移动。这非常适合需要 原地重构 数组或在向前扫描时检测特定模式的问题。
让我们来看一个经典例子。
Source:
Problem 2 — Remove Duplicates from Sorted Array
给定一个按非递减顺序排序的整数数组 nums，请 原地 删除重复元素，使每个唯一元素只出现一次。返回唯一元素的数量 k。
直观的做法可能是使用集合收集唯一值并重新构建数组——但题目明确要求 原地 解法，且只能使用 O(1) 额外空间。采用同向双指针技术（通常称为 慢指针 与 快指针）可以高效地解决此问题。
（后续解法将在下一篇文章中继续。）
使用 O(1) 额外内存的原地解法
使用集合会导致 O(n) 的空间开销，违背题意。
class Solution:
def removeDuplicates(self, nums: List[int]) -> int:
seen = set()
result = []
for num in nums:
if num not in seen:
seen.add(num)
result.append(num)
# This doesn't satisfy the in‑place constraint
for i in range(len(result)):
nums[i] = result[i]
return len(result)除了违反空间限制，这种做法还创建了我们不需要的辅助数据结构。
双指针 模式可以提供更简洁且符合要求的解法。
优化：同向双指针
思路： 使用 slow 指针记录下一个唯一元素应写入的位置，fast 指针向前扫描数组寻找新的唯一值。每当 fast 发现的值与 slow 所指的值不同时，就把 slow 前移并将该新值写入 slow 所在位置。
class Solution:
def removeDuplicates(self, nums: List[int]) -> int:
# 'slow' marks the boundary of our unique‑elements section
slow = 0
# 'fast' scans ahead to discover new unique elements
for fast in range(1, len(nums)):
# When fast finds a value different from slow's position,
# a new unique element has been discovered
if nums[fast] != nums[slow]:
slow += 1 # Expand the unique section
nums[slow] = nums[fast] # Write the new unique value in place
# slow is now the index of the last unique element
# so the count of unique elements is slow + 1
return slow + 1- 时间复杂度： O(n) —
fast只遍历数组一次。 - 空间复杂度： O(1) — 完全在原地完成，没有额外的数据结构。
这里的巧妙之处在于两指针协同工作：fast 负责探索，slow 负责写入。它们永不冲突，因为 slow 永远在 fast 的同位置或其后方。
何时使用此模式
- 当处理 已排序 的数组或字符串时（这是使用相反方向指针的一个重要提示）。
- 当问题要求你找到满足条件的 一对（或三元组）元素时。
- 当你需要 就地 重构或去重数组，且空间复杂度为 O(1) 时。
- 当暴力解法涉及对同一线性数据结构的 嵌套循环 时——这几乎总是表明可以使用双指针将其压缩到 O(n)。
接下来做什么？练习
前往 LeetCode 并尝试 Two Pointers problem list —— 该标签下有超过 200 道题目。先从简单题开始培养直觉，然后再挑战中等难度。
接下来可以尝试的几个好题
- Container With Most Water (Medium) — opposite‑direction pointers.
- 3Sum (Medium) — two pointers inside an outer loop.
- Linked List Cycle (Easy) — fast & slow pointers on a linked list.
注意： 与滑动窗口模式一样，Two Pointers 并不总是唯一的有效方法。当满足特定条件时——如已排序的数据、原地约束、配对/子集问题——它是一个强大的工具——但在使用之前请始终思考该模式是否真正适合。
在下一篇文章中再见，届时会介绍另一个编码模式！