[!info] related notes 两数之和2 滑动窗口 二分查找

双指针

双指针用两个位置维护搜索边界或已处理区域。移动规则必须保持对应不变量：有序配对可以排除候选区间，原地去重维护已处理前缀，链表环检测则利用不同步速。若两个指针总共只移动 O(n) 次且每步更新为 O(1)，主过程就是 O(n)。

分类

1. 对撞指针（Opposite Direction）

两端向中间收缩，适用于有序数组上的配对问题。

def two_sum_sorted(arr, target):
    lo, hi = 0, len(arr) - 1
    while lo < hi:
        s = arr[lo] + arr[hi]
        if s == target:
            return [lo, hi]
        elif s < target:
            lo += 1      # 排除 arr[lo] 与 arr[lo+1..hi] 的所有配对
        else:
            hi -= 1      # 排除 arr[hi] 与 arr[lo..hi-1] 的所有配对
    return []

2. 同向指针（Same Direction / Fast-Slow）

两个指针同向移动，通常一个快一个慢，适用于去重、分区、链表环检测等。

def remove_duplicates(nums):
    """非递减数组原地去重，返回新长度"""
    if not nums:
        return 0
    slow = 0
    for fast in range(1, len(nums)):
        if nums[fast] != nums[slow]:
            slow += 1
            nums[slow] = nums[fast]
    return slow + 1

3. 滑动窗口（Sliding Window）

本质是同向双指针的特化：left 和 right 维护一个满足条件的窗口。参见 滑动窗口。

常见模式

模式	指针类型	典型题
两数之和（有序）	对撞	LeetCode 167
三数之和	排序 + 对撞	LeetCode 15
盛最多水的容器	对撞	LeetCode 11
回文判断	对撞	LeetCode 125
移除元素	同向	LeetCode 27
合并有序数组	同向（从后往前）	LeetCode 88
链表环检测	快慢指针	LeetCode 141

关键直觉

• 有序是上面数值配对时安全排除候选的前提；回文检查、盛水容器等对撞指针使用不同的不变量，并不要求数组按值排序。排序预处理后再线性扫描的总复杂度仍为 $O(n \log n)$。
• 同向指针的核心是”慢指针维护已处理区，快指针探索未知区”。
• 必须说明每次移动为何安全以及何时终止；指针数量本身不能保证线性复杂度。

相关笔记

• 滑动窗口
• 二分查找
• 排序算法总结
• 算法面试题型 MOC