数据结构与算法 / 系统课时
双指针遍历数组
双指针遍历数组
双指针不是固定代码模板,而是同时维护两个位置,通过单调移动减少重复扫描。本课分别用同向指针整理有效区间、用相向指针搜索有序数组,并说明算法正确性依赖的循环不变式。
学习目标
- 理解同向双指针和相向双指针的适用条件。
- 能为每个指针定义清晰语义和移动规则。
- 能使用双指针把常见数组问题降为 。
两类双指针模式
同向双指针通常由快指针负责扫描,慢指针维护已经处理好的有效区间。例如移动零时,慢指针表示下一个非零元素应写入的位置;它左侧始终是顺序正确的非零区间。
相向双指针从数组两端向中间收缩,通常依赖有序性或其他单调关系。升序数组中,两端之和过小就移动左指针,过大就移动右指针,从而一次排除一批不可能组合。

正确性来自不变式
使用双指针前应回答三个问题:每个指针表示什么、哪个条件触发移动、移动后保持什么性质。若某个分支不移动任何指针,循环可能无法终止。
相向双指针不能脱离单调性直接套用。无序数组中,根据当前和大小移动左右端点可能跳过正确答案;此时应先排序并评估排序成本,或改用哈希表。
主示例:整理数组并搜索有序区间
下面的 Python 示例在一个文件中演示两类模式。move_zeros 原地移动零并保持非零元素相对顺序;two_sum_sorted 在升序数组中返回一组满足目标和的下标。
python
from typing import Optional
def move_zeros(nums: list[int]) -> None:
slow = 0
for fast in range(len(nums)):
if nums[fast] == 0:
continue
# slow 左侧始终保存已处理且顺序正确的非零元素。
nums[slow], nums[fast] = nums[fast], nums[slow]
slow += 1
def two_sum_sorted(
nums: list[int],
target: int,
) -> Optional[tuple[int, int]]:
left = 0
right = len(nums) - 1
while left < right:
current = nums[left] + nums[right]
if current == target:
return left, right
if current < target:
left += 1
else:
right -= 1
return None
def main() -> None:
values = [0, 3, 0, 1, 0, 5]
move_zeros(values)
print("移动零后:", values)
sorted_values = [1, 2, 4, 7, 11, 15]
result = two_sum_sorted(sorted_values, 15)
print("目标值 15 的下标:", result)
if result is not None:
left, right = result
print("对应元素:", sorted_values[left], sorted_values[right])
if __name__ == "__main__":
main()运行命令:
bash
python two_pointers.py预期输出:
text
移动零后: [3, 1, 5, 0, 0, 0]
目标值 15 的下标: (2, 4)
对应元素: 4 11两个指针都只沿一个方向移动,每个位置最多被有限次处理,因此时间复杂度为 。两个函数都在原数组或常数个变量上工作,额外空间复杂度为 。
边界与常见错误
寻找两个不同元素时,循环通常使用 left < right,否则可能让同一位置与自身配对。移动零时交换写法即使 slow == fast 也安全,只会发生一次自交换。
原地覆盖算法必须确保读取位置尚未被破坏。若慢指针语义在“最后一个有效位置”和“下一个写入位置”之间混用,常会出现漏写或多移动一格的问题。
按自己的节奏,确认真正理解。