双指针与滑动窗口 · 数据结构与算法

为什么需要它

直觉理解

定义

双指针

Two indexes that move toward each other (or in the same direction) so each element is visited once.

两个下标相向（或同向）移动，让每个元素只被访问一次。

滑动窗口

A range [left, right) over the list that moves forward, updating a running total instead of recomputing it.

列表上一个向前移动的区间 [left, right)，每次更新累计值，而不是重新计算。

示例

1
2
3
4
5
6
7
8
9
10
11
12
13

def pair_sum(xs, target):
    left, right = 0, len(xs) - 1
    while left < right:
        total = xs[left] + xs[right]
        if total == target:
            return (xs[left], xs[right])
        if total < target:
            left += 1
        else:
            right -= 1
    return None

print(pair_sum([1, 3, 4, 6, 9, 11], 13))

1
2
3
4
5
6
7
8

sales = [4, 2, 7, 1, 8, 3, 5]
k = 3
window = sum(sales[:k])
best = window
for i in range(k, len(sales)):
    window += sales[i] - sales[i - k]
    best = max(best, window)
print(best)

常见错误

小测验

1
2
3
4
5
6
7

xs = [1, 2, 3, 4, 5]
left, right = 0, len(xs) - 1
while left < right:
    xs[left], xs[right] = xs[right], xs[left]
    left += 1
    right -= 1
print(xs)

动手练习

3 道练习，分三层：先预测程序的输出，再按新需求改程序，最后从零写一个。代码在浏览器里运行，提交马上判题。

1. 预测输出跟踪指针

   准确写出这段程序的输出。

2. 改需求一遍去重

   dedupe(xs) 收到一个有序列表，返回去掉重复后的列表。里面那层循环对每个元素都把 out 扫一遍（O(n²)）。既然列表有序，重复的元素只可能等于最后一个保留下来的元素。利用这一点把它改成 O(n)。

3. 从零写最好的窗口

   写函数 best_window(xs, k)，返回 xs 中任意连续 k 个数之和的最大值（假设 len(xs) ≥ k ≥ 1）。用滑动窗口：O(n)。

本课术语