数据结构与算法 / 系统课时

双指针遍历数组

双指针遍历数组

双指针不是固定代码模板,而是同时维护两个位置,通过单调移动减少重复扫描。本课分别用同向指针整理有效区间、用相向指针搜索有序数组,并说明算法正确性依赖的循环不变式。

学习目标

  • 理解同向双指针和相向双指针的适用条件。
  • 能为每个指针定义清晰语义和移动规则。
  • 能使用双指针把常见数组问题降为 O(n)O(n)。

两类双指针模式

同向双指针通常由快指针负责扫描,慢指针维护已经处理好的有效区间。例如移动零时,慢指针表示下一个非零元素应写入的位置;它左侧始终是顺序正确的非零区间。

相向双指针从数组两端向中间收缩,通常依赖有序性或其他单调关系。升序数组中,两端之和过小就移动左指针,过大就移动右指针,从而一次排除一批不可能组合。

同向与相向双指针对比

正确性来自不变式

使用双指针前应回答三个问题:每个指针表示什么、哪个条件触发移动、移动后保持什么性质。若某个分支不移动任何指针,循环可能无法终止。

相向双指针不能脱离单调性直接套用。无序数组中,根据当前和大小移动左右端点可能跳过正确答案;此时应先排序并评估排序成本,或改用哈希表。

主示例:整理数组并搜索有序区间

下面的 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

两个指针都只沿一个方向移动,每个位置最多被有限次处理,因此时间复杂度为 O(n)O(n)。两个函数都在原数组或常数个变量上工作,额外空间复杂度为 O(1)O(1)。

边界与常见错误

寻找两个不同元素时,循环通常使用 left < right,否则可能让同一位置与自身配对。移动零时交换写法即使 slow == fast 也安全,只会发生一次自交换。

原地覆盖算法必须确保读取位置尚未被破坏。若慢指针语义在“最后一个有效位置”和“下一个写入位置”之间混用,常会出现漏写或多移动一格的问题。

按自己的节奏,确认真正理解。

目录与阅读设置

阅读设置

17

记录一个想法

双指针遍历数组

0 / 10000 · 笔记保存到账号。未提交的修改会在关闭、离开或刷新后丢失。

登录哪都通