双指针法概述

适用场景判断使用双指针的典型信号：
题目要求 “原地修改”（不使用额外空间）
题目给出有序数组
要求保持 “相对顺序”
题目和两端比较有关

双指针分类

经典算法题：移动零（LeetCode 283）

题目描述：给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序，且必须原地修改数组。

示例：
输入：nums = [0, 1, 0, 3, 12]
输出：[1, 3, 12, 0, 0]

快慢指针解法（时间 O(n)，空间 O(1)）

核心思路：
slow 指针：记录下一个非零元素应该放置的位置
fast 指针：遍历整个数组，寻找非零元素
遇到非零元素时，将其赋值到 slow 位置，然后 slow 前进
遍历结束后，slow 之后的位置全部补 0

from typing import List

class Solution:
    def moveZeroes(self, nums: List[int]) -> None:
        """Do not return anything, modify nums in-place instead."""
        slow = 0  # 记录非零元素该放的位置
        # fast 指针遍历整个数组
        for fast in range(len(nums)):
            if nums[fast] != 0:  # 将非零元素移动到 slow 指针位置
                nums[slow] = nums[fast]
                slow += 1
        # 前面的非零元素已处理完，剩下的位置全部补 0
        for i in range(slow, len(nums)):
            nums[i] = 0

代码执行示例

以 nums = [2, 0, 3, 0, 9] 为例：
fast=0：nums[0]=2≠0 → nums[0]=2，slow=1
fast=1：nums[1]=0 → 跳过
fast=2：nums[2]=3≠0 → nums[1]=3，slow=2
fast=3：nums[3]=0 → 跳过
fast=4：nums[4]=9≠0 → nums[2]=9，slow=3
补零：nums[3] = 0，nums[4] = 0
最终数组：[2, 3, 9, 0, 0]

双指针核心技巧总结

对向指针（左右指针）

初始化：left = 0，right = len(nums) - 1
循环条件：while left <= right
移动逻辑：根据比较结果，让 left 右移或 right 左移，向中间逼近

快慢指针

初始化：slow = 0，fast 从 0 开始遍历
核心：fast 负责探索，slow 负责收集有效结果
典型操作：覆盖 / 交换，实现原地修改

指针操作本质

一次遍历：避免嵌套循环，时间复杂度优化到 O(n)
不额外数组：空间复杂度优化到 O(1)
整理结果：遍历完成后，对剩余位置做统一处理（如补零）

双指针适用场景速查