第3章：双指针与滑动窗口

线性时间的艺术

双指针技巧是算法题中最优雅的技巧之一。它的核心思想简单却强大：通过维护两个或多个指针的相对运动，将原本需要嵌套循环的 $O(n^2)$ 问题优化到 $O(n)$。对于习惯函数式编程的你来说，可以将双指针理解为对序列的一种有状态遍历（stateful traversal），其中指针位置就是状态。

本章我们将深入探讨四种双指针模式：相向双指针、快慢指针、滑动窗口和多指针协作。每种模式都有其特定的适用场景和思维框架。掌握这些模式后，你将能够快速识别并解决大量的数组和字符串问题。

3.1 相向双指针：有序数组的利用

相向双指针是最直观的双指针技巧。两个指针分别从数组的两端开始，根据某种条件向中间移动，直到相遇。这种技巧特别适合处理有序数组，因为我们可以利用排序的单调性来决定指针的移动方向。

核心思想

相向双指针的本质是一种贪心策略：每次移动都基于当前状态做出最优决策，从而避免遍历所有可能的组合。考虑两数之和问题：

def two_sum_sorted(nums: List[int], target: int) -> List[int]:
    left, right = 0, len(nums) - 1

    while left < right:
        current_sum = nums[left] + nums[right]
        if current_sum == target:
            return [left, right]
        elif current_sum < target:
            left += 1  # 需要更大的和
        else:
            right -= 1  # 需要更小的和

    return []

为什么这个算法是正确的？关键在于单调性：

当 nums[left] + nums[right] < target 时，固定 left，无论 right 如何左移，和只会更小
当 nums[left] + nums[right] > target 时，固定 right，无论 left 如何右移，和只会更大

因此，每次移动都可以安全地排除一行或一列的可能性，这就是为什么时间复杂度是 $O(n)$ 而不是 $O(n^2)$。

典型例题：盛最多水的容器 (LeetCode 11)

这道题展示了相向双指针的精髓：如何通过贪心选择来避免穷举。

def max_area(height: List[int]) -> int:
    left, right = 0, len(height) - 1
    max_water = 0

    while left < right:
        width = right - left
        min_height = min(height[left], height[right])
        max_water = max(max_water, width * min_height)

        # 关键：移动较矮的一边
        if height[left] < height[right]:
            left += 1
        else:
            right -= 1

    return max_water

移动策略的正确性证明：设当前容器的容量为 $V = \min(h[l], h[r]) \times (r - l)$。不失一般性，假设 $h[l] < h[r]$：

如果移动 right，新容量 $V' = \min(h[l], h[r-1]) \times (r-1-l) \leq h[l] \times (r-1-l) < V$
如果移动 left，新容量可能增大（如果 $h[l+1] > h[l]$）

因此，移动较矮的一边是唯一可能获得更大容量的选择。

三数之和 (LeetCode 15)

三数之和展示了如何将双指针嵌入到更大的算法框架中：

def three_sum(nums: List[int]) -> List[List[int]]:
    nums.sort()  # 排序是关键
    result = []
    n = len(nums)

    for i in range(n - 2):
        # 跳过重复元素
        if i > 0 and nums[i] == nums[i-1]:
            continue

        # 固定第一个数，转化为两数之和
        left, right = i + 1, n - 1
        target = -nums[i]

        while left < right:
            current_sum = nums[left] + nums[right]
            if current_sum == target:
                result.append([nums[i], nums[left], nums[right]])

                # 跳过重复解
                while left < right and nums[left] == nums[left + 1]:
                    left += 1
                while left < right and nums[right] == nums[right - 1]:
                    right -= 1

                left += 1
                right -= 1
            elif current_sum < target:
                left += 1
            else:
                right -= 1

    return result

这里的关键技巧：

降维思想：固定一个维度，将三数问题转化为两数问题
去重处理：通过跳过重复元素避免重复解
时间复杂度：$O(n^2)$，比暴力的 $O(n^3)$ 优化了一个数量级

3.2 快慢指针：链表与数组去重

快慢指针（也称为龟兔赛跑算法）是另一种重要的双指针技巧。两个指针以不同的速度遍历序列，用于检测环、寻找中点或进行原地去重。

环形链表检测 (LeetCode 142)

Floyd 判圈算法是快慢指针的经典应用：

def detect_cycle(head: ListNode) -> ListNode:
    # 第一阶段：判断是否有环
    slow = fast = head

    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
        if slow == fast:
            break
    else:
        return None  # 无环

    # 第二阶段：找到环的入口
    slow = head
    while slow != fast:
        slow = slow.next
        fast = fast.next

    return slow

数学证明：设链表起点到环入口的距离为 $a$，环的长度为 $b$。当快慢指针相遇时：

慢指针走过的距离：$s = a + k_1 \cdot b + m$（其中 $m$ 是在环内的偏移）
快指针走过的距离：$2s = a + k_2 \cdot b + m$

由 $2s - s = s$ 得：$a + m = (k_2 - 2k_1) \cdot b$

这意味着从相遇点再走 $a$ 步，恰好回到环的入口（模 $b$ 意义下）。

数组原地去重 (LeetCode 80)

快慢指针在数组去重中的应用展示了其"写入"功能：

def remove_duplicates(nums: List[int]) -> int:
    if len(nums) <= 2:
        return len(nums)

    # slow: 下一个写入位置
    # fast: 当前检查位置
    slow = 2

    for fast in range(2, len(nums)):
        # 最多保留两个重复
        if nums[fast] != nums[slow - 2]:
            nums[slow] = nums[fast]
            slow += 1

    return slow

这里的不变式：

nums[0:slow] 始终满足"最多两个重复"的条件
slow 指向下一个可以写入的位置
fast 扫描所有元素

寻找链表中点

快慢指针的另一个优雅应用：

def find_middle(head: ListNode) -> ListNode:
    slow = fast = head

    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next

    return slow

当快指针到达末尾时，慢指针恰好在中点。这个技巧常用于：

链表归并排序（找中点后分治）
判断回文链表（找中点后翻转比较）
将链表转为二叉搜索树（中点作为根）

3.3 滑动窗口：最长/最短子串问题

滑动窗口是处理子数组/子串问题的利器。它维护一个动态的窗口，通过扩展右边界和收缩左边界来寻找满足条件的最优解。

滑动窗口模板

def sliding_window_template(s: str) -> int:
    left = 0
    window = {}  # 窗口状态
    result = 0

    for right in range(len(s)):
        # 扩展窗口
        c = s[right]
        window[c] = window.get(c, 0) + 1

        # 收缩窗口（当窗口不满足条件时）
        while not is_valid(window):
            d = s[left]
            window[d] -= 1
            if window[d] == 0:
                del window[d]
            left += 1

        # 更新结果
        result = max(result, right - left + 1)

    return result

关键要素：

窗口状态：用哈希表或数组维护窗口内元素的状态
扩展条件：何时扩展右边界（通常是遍历）
收缩条件：何时收缩左边界（违反约束时）
更新时机：何时更新答案（窗口有效时）

无重复字符的最长子串 (LeetCode 3)

def length_of_longest_substring(s: str) -> int:
    char_index = {}  # 字符最后出现的位置
    left = 0
    max_length = 0

    for right in range(len(s)):
        if s[right] in char_index and char_index[s[right]] >= left:
            # 发现重复，移动左边界
            left = char_index[s[right]] + 1

        char_index[s[right]] = right
        max_length = max(max_length, right - left + 1)

    return max_length

优化技巧：直接跳转而不是逐步移动 left，时间复杂度保持 $O(n)$。

找到字符串中所有字母异位词 (LeetCode 438)

def find_anagrams(s: str, p: str) -> List[int]:
    if len(p) > len(s):
        return []

    # 目标频率
    target = {}
    for c in p:
        target[c] = target.get(c, 0) + 1

    # 滑动窗口
    window = {}
    result = []
    formed = 0  # 满足频率要求的字符数
    required = len(target)

    for right in range(len(s)):
        # 扩展窗口
        c = s[right]
        window[c] = window.get(c, 0) + 1
        if c in target and window[c] == target[c]:
            formed += 1

        # 收缩窗口（固定大小）
        if right >= len(p):
            left_char = s[right - len(p)]
            if left_char in target and window[left_char] == target[left_char]:
                formed -= 1
            window[left_char] -= 1
            if window[left_char] == 0:
                del window[left_char]

        # 检查是否匹配
        if formed == required and right >= len(p) - 1:
            result.append(right - len(p) + 1)

    return result

这里使用了固定大小的滑动窗口，配合 formed 计数器优化比较效率。

长度最小的子数组 (LeetCode 209)

寻找最短窗口的典型问题：

def min_subarray_len(target: int, nums: List[int]) -> int:
    left = 0
    current_sum = 0
    min_length = float('inf')

    for right in range(len(nums)):
        current_sum += nums[right]

        # 收缩窗口（当满足条件时继续收缩）
        while current_sum >= target:
            min_length = min(min_length, right - left + 1)
            current_sum -= nums[left]
            left += 1

    return min_length if min_length != float('inf') else 0

注意这里的收缩条件：当窗口满足条件时，我们尝试收缩以找到最小窗口。这与寻找最长窗口的逻辑相反。

3.4 多指针协作：三数之和、四数之和

当问题涉及多个元素的组合时，我们可以使用多个指针协同工作。核心思想是固定部分维度，将高维问题降到可以用双指针解决的维度。

最接近的三数之和 (LeetCode 16)

def three_sum_closest(nums: List[int], target: int) -> int:
    nums.sort()
    n = len(nums)
    closest_sum = float('inf')

    for i in range(n - 2):
        left, right = i + 1, n - 1

        while left < right:
            current_sum = nums[i] + nums[left] + nums[right]

            # 更新最接近的和
            if abs(current_sum - target) < abs(closest_sum - target):
                closest_sum = current_sum

            if current_sum < target:
                left += 1
            elif current_sum > target:
                right -= 1
            else:
                return target  # 找到精确匹配

    return closest_sum

四数之和 (LeetCode 18)

四数之和展示了如何递归地应用降维思想：

def four_sum(nums: List[int], target: int) -> List[List[int]]:
    def k_sum(nums: List[int], target: int, k: int, start: int) -> List[List[int]]:
        result = []

        # 递归基：两数之和
        if k == 2:
            left, right = start, len(nums) - 1
            while left < right:
                current_sum = nums[left] + nums[right]
                if current_sum == target:
                    result.append([nums[left], nums[right]])
                    # 跳过重复
                    while left < right and nums[left] == nums[left + 1]:
                        left += 1
                    while left < right and nums[right] == nums[right - 1]:
                        right -= 1
                    left += 1
                    right -= 1
                elif current_sum < target:
                    left += 1
                else:
                    right -= 1
            return result

        # 递归：固定一个数，求 (k-1) 数之和
        for i in range(start, len(nums) - k + 1):
            # 跳过重复
            if i > start and nums[i] == nums[i - 1]:
                continue

            # 剪枝：最小和大于目标
            if nums[i] * k > target:
                break

            # 剪枝：最大和小于目标
            if nums[-1] * k < target:
                break

            sub_results = k_sum(nums, target - nums[i], k - 1, i + 1)
            for sub_result in sub_results:
                result.append([nums[i]] + sub_result)

        return result

    nums.sort()
    return k_sum(nums, target, 4, 0)

这个通用的 k-sum 解法展示了：

递归降维：k 数之和 → (k-1) 数之和 → ... → 两数之和
剪枝优化：利用有序性提前终止
去重处理：在每个层级都要处理重复

接雨水 (LeetCode 42) - 双指针解法

虽然接雨水有多种解法，双指针解法最为优雅：

def trap(rain_water: List[int]) -> int:
    if not rain_water:
        return 0

    left, right = 0, len(rain_water) - 1
    left_max = right_max = 0
    water = 0

    while left < right:
        if rain_water[left] < rain_water[right]:
            if rain_water[left] >= left_max:
                left_max = rain_water[left]
            else:
                water += left_max - rain_water[left]
            left += 1
        else:
            if rain_water[right] >= right_max:
                right_max = rain_water[right]
            else:
                water += right_max - rain_water[right]
            right -= 1

    return water

核心洞察：

某个位置能接的水量取决于左右两边的最大高度中的较小者
通过双指针，我们总是从较矮的一边计算，保证另一边有足够的高度"兜住"水

本章小结

双指针技巧的核心价值在于将问题的搜索空间从 $O(n^2)$ 或更高降到 $O(n)$。关键是理解每种模式的适用场景：

相向双指针：适用于有序数组，利用单调性进行决策 - 两数之和/三数之和 - 容器盛水 - 数组中的配对问题
快慢指针：适用于环检测、链表操作和原地修改 - 环形链表检测 - 寻找中点 - 原地去重
滑动窗口：适用于连续子数组/子串问题 - 最长/最短满足条件的子串 - 固定大小窗口的统计 - 字符串匹配
多指针协作：适用于多元素组合问题 - k-sum 问题 - 多维搜索空间的降维

从函数式编程的角度看，双指针可以理解为对序列的一种特殊折叠（fold）操作，其中累积状态是指针位置，而折叠函数根据当前元素和状态决定下一步的指针移动。

常见陷阱与错误 (Gotchas)

1. 边界条件处理不当

# 错误：可能越界
while left <= right:  # 应该是 left < right
    if nums[left] + nums[right] == target:
        return [left, right]
    # ...

# 错误：忘记检查数组长度
def two_pointer(nums):
    left, right = 0, len(nums) - 1  # nums 为空时 right = -1

2. 去重逻辑错误

# 错误：去重时机不对
for i in range(n):
    if i > 0 and nums[i] == nums[i-1]:
        continue  # 可能跳过所有相同元素

# 正确：只在找到解后去重
if found_solution:
    while left < right and nums[left] == nums[left + 1]:
        left += 1

3. 滑动窗口的收缩条件

# 错误：用 if 而不是 while
if window_invalid:  # 应该用 while
    left += 1

# 错误：更新答案的时机
while window_invalid:
    left += 1
result = max(result, right - left + 1)  # 可能在无效窗口时更新

4. 指针移动策略

# 错误：盛水容器中移动错误的指针
if height[left] < height[right]:
    right -= 1  # 应该移动较矮的 left

5. 整数溢出

# 在某些语言中可能溢出
current_sum = nums[i] + nums[j] + nums[k]

# 更安全的做法
if nums[i] > target - nums[j] - nums[k]:  # 避免直接相加
    # ...

调试技巧

打印指针轨迹：在循环中打印指针位置和当前状态
检查不变式：确保循环不变式始终成立
手动模拟：用小例子手动执行算法
可视化：画图理解指针的移动过程

记住，双指针的正确性往往依赖于某种单调性或不变式。在实现前，先明确这个性质是什么，这样能避免大部分错误。