[!info] related notes 两数之和2 滑动窗口 [[binary-search-basics|二分查找基础]]

双指针

本质是利用数据的单调性（Monotonicity）来规避冗余计算——当一个指针的移动能确定地排除一批候选答案时，复杂度就从 $O(n^2)$ 降到 $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):
    """原地去重，返回新长度"""
    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)$ 常能换来 $O(n)$ 的主过程。
• 同向指针的核心是”慢指针维护已处理区，快指针探索未知区”。
• 每次移动指针都应确定性地排除至少一个元素，否则退化为暴力。

相关笔记

• 滑动窗口
• [[binary-search-basics|二分查找基础]]
• 排序算法总结
• 算法面试题型 MOC