外观
07 - 双指针与滑动窗口:把嵌套扫描降为线性处理
前置阅读:04 - Hash 表原理与工程应用、A - 算法正确性、测试与基准方法。
单调队列见05 - 栈与队列的解题模型。TCP 的滑动窗口是流量控制协议,与本文的区间扫描模型含义不同,见网络 06。
摘要
寻找最长无重复子串时,逐个枚举连续区间会产生平方级数量的候选。滑动窗口通过复用上一轮的状态,避免从头检查每个区间。本文先解释双指针的三种基本模型,再说明边界为什么可以移动、哪些候选可以安全排除,以及何时不能直接套用窗口模板。
1. 三类双指针
这里的“指针”是用来记录位置的变量:在数组中通常是下标,在链表中则是节点引用。双指针不是一套固定代码,而是让两个位置配合移动,减少重复扫描。
| 模型 | 两个位置如何配合 | 典型问题 |
|---|---|---|
| 相向指针 | 从两端向中间移动,每次排除一侧候选 | 有序数组两数之和、回文判断 |
| 快慢指针 | 以不同速度遍历,或分别负责读取和写入 | 链表环、原地去重 |
| 同向窗口 | 左右边界沿同一方向移动,维护一个连续区间 | 连续区间统计、最长无重复子串 |
滑动窗口中的“窗口”就是当前正在处理的连续区间。本文用 [left, right] 表示包含两端的闭区间,长度为 right - left + 1。右边界加入新元素,左边界排除旧元素;程序只更新受影响的状态,不必重新扫描整个窗口。这种只处理变化部分的方式称为增量维护。
固定窗口保持长度不变,每次前进时加入一个元素、移除一个元素;可变窗口则根据条件调整长度。下面先讨论可变窗口:要求区间内没有重复字符,并寻找最长的合法区间。“合法”在这里表示满足无重复条件。
2. 最长无重复子串
子串是原字符串中连续的一段字符。对每个右端点,只需要找到以它结尾的最长无重复子串,再从这些结果中取最大长度。设新字符上次出现在位置 previous:如果这个位置仍在窗口内,新的左端点必须越过它,否则两个相同字符会同时留在窗口中。若上次位置已在窗口外,就不需要收缩。
last 保存每个字符最近出现的位置,left 保存当前窗口起点,best 保存目前找到的最大长度。下面是需要放入 Java 类中的局部方法,要求 text 非 null;空字符串返回 0。
java
import java.util.HashMap;
import java.util.Map;
static int longestUnique(String text) {
Map<Character, Integer> last = new HashMap<>();
int left = 0;
int best = 0;
for (int right = 0; right < text.length(); right++) {
char ch = text.charAt(right);
Integer previous = last.put(ch, right);
if (previous != null && previous >= left) {
left = previous + 1;
}
best = Math.max(best, right - left + 1);
}
return best;
}last.put(ch, right) 更新最近位置,同时返回更新前的位置。若 previous >= left,令 left = previous + 1:起点更早的区间都会同时包含这两个字符,因此排除它们不会漏掉合法答案。这个重复也会保留在任何继续向右扩展的区间中,所以已经排除的起点无需重新考虑。每轮更新 best 前,[left, right] 都无重复,且是以 right 结尾的最长合法窗口。
右边界扫描一次,左边界只向右移动。在哈希表操作平均为常数时间的假设下,时间复杂度为 O(n),其中 n 是 text.length();表的额外空间取决于不同 char 的数量。这里的表保存的是整个已扫描部分的最近位置,允许保留窗口外的记录,是否有效由 previous >= left 判断。
Java 的 UTF-16 用 16 位编码单元表示文本,char 对应一个编码单元。某些字符(如示例中的 😀)需要两个 char,所以本方法返回的是按编码单元计算的长度。Unicode Code Point(码点)是 Unicode 为字符分配的编号;若按码点判断重复,应改用 codePoints(),下标和长度也随之按码点计算。第 6 节展示这种写法。用户感知的一个字符还可能由多个码点组成,两种写法都不能直接等同于用户看到的字符数。
3. 为什么窗口能工作
前面的算法直接跳过重复位置。更一般的实现会逐个移除左端元素,但都需要满足两个条件:
- 右边界加入元素后,能快速更新状态;
- 条件不满足时,左边界前进能逐步恢复合法性。
如果移除左侧元素无法恢复条件,或最优解依赖被丢弃的复杂历史,就不适合直接套滑动窗口。
对于“最长合法窗口”,常见的处理顺序如下。这是说明更新过程的伪代码:
text
for right 向右扩展:
把 right 对应元素加入状态
while 当前窗口不合法:
从状态移除 left 对应元素
left++
用当前合法窗口更新答案“何时更新答案”取决于目标。最长合法窗口通常先恢复合法性,再记录长度。最短满足窗口则在满足目标时记录长度,并继续收缩,直到不再满足条件。
例如在非负数数组中寻找“和至少为 K 的最短区间”(这里取 K > 0),扩展窗口不会减小和,收缩不会增大和。达到 K 后,可以先记录答案,再尝试移除左端元素,寻找更短的满足区间;不再满足时,再扩展右边界。这种变化只朝一个方向的性质称为单调性,它决定了哪些候选可以排除。两种目标不能只替换比较符号机械转换。
窗口算法的证明需要说明:
left和right都不会回退,因此移动总次数为O(n);还需计入每次状态更新的成本,才能得到总时间复杂度;- 被左边界排除的候选不可能参与更优答案;
- 状态能正确描述窗口:计数表要随加入、移除而更新;最近位置表则要检查记录是否仍在窗口内。
每轮循环前后都成立的约束称为循环不变量。第 2 节的不变量是“更新答案时窗口无重复,且左边界不会回退”。即使代码里有 for 和 while 两层循环,只要两个边界的累计移动次数是线性的、每步状态更新成本为常数,也不会变成平方级扫描。
4. 快慢指针判断链表环
链表有环,表示沿 next 访问节点时会再次遇到已经访问过的节点。下面是局部方法,依赖调用方定义带有 Node next 字段的节点类型,并假设遍历期间链表不被修改。slow 每轮走一步,fast 每轮走两步;== 比较的是节点引用,两个节点的值相同不表示遇到了同一个节点。
java
static boolean hasCycle(Node head) {
Node slow = head;
Node fast = head;
while (fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
if (slow == fast) return true;
}
return false;
}没有环时,快指针会到达链表末尾。循环先检查 fast 和 fast.next,再访问 fast.next.next,避免对空引用继续取字段;空链表直接返回 false。
如果存在环,两者最终都会进入环。设环长为 c,每轮快指针比慢指针多走一步,因此它们在环上的相对距离每轮变化一格,至多再经过 c 轮就会相遇。比较放在移动之后,避免把初始化时都指向 head 误判为有环。按可达的不同节点数计,时间复杂度为 O(n),额外空间为 O(1)。
5. 相向指针求有序两数之和
下面的局部方法要求 values 非 null,并按非递减顺序排列,即允许相邻值相等。它返回一对不同下标,找不到时返回 [-1, -1];有多组答案时不保证返回全部答案。
有序性决定了移动规则:
- 当前和小于
target时,固定left并选择更小的右侧值,只会得到更小或相等的和。因此当前左端元素不可能与剩余区间中的元素组成答案,可以令left++。 - 当前和大于
target时,固定right并选择更大的左侧值,只会得到更大或相等的和。因此可以排除当前右端元素,令right--。
java
static int[] twoSumSorted(int[] values, int target) {
int left = 0;
int right = values.length - 1;
while (left < right) {
long sum = (long) values[left] + values[right];
if (sum == target) return new int[] { left, right };
if (sum < target) left++;
else right--;
}
return new int[] { -1, -1 };
}left < right 保证不会使用同一个元素两次;空数组和单元素数组返回 [-1, -1]。两端每轮至少排除一个元素,所以扫描时间为 O(n),额外空间为 O(1)。这个复杂度不包含预先排序的成本;若先排序,还需要考虑原始下标如何保留。
先把一个操作数转为 long,使加法按 long 计算,避免两个 int 相加溢出后再转换已经错误的结果。
6. 完整可运行示例:三类双指针
下面的类对应文件名 TwoPointerDemo.java,包含 main 入口。数组和字符串参数要求非 null;两数之和与去重要求数组按非递减顺序排列。
这个示例的快慢指针用于原地去重:fast 读取输入,slow 指向下一个写入位置。[0, slow) 是包含 0、不包含 slow 的左闭右开区间,始终保存已经去重的结果。有序数组的重复值相邻,因此只需与结果区最后一个值比较。写入位置不会超过当前读取位置,所以不会覆盖尚未读取的元素。方法会修改原数组,返回有效前缀长度;该长度以后的内容不属于去重结果。空数组返回 0。
示例中的 longestUnique 按码点计算,区别于第 2 节的 char 版本。它先创建码点数组,因此还需要与码点数量成正比的额外空间。
java
import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;
/**
* 可运行示例:双指针与滑动窗口:把嵌套扫描降为线性处理。
* 重点观察核心状态如何更新,以及边界输入如何处理。
*/
public class TwoPointerDemo {
static int[] twoSumSorted(int[] a, int target) {
int left = 0,
right = a.length - 1;
while (left < right) {
// 用 long 计算,避免两个 int 相加溢出。
long sum = (long) a[left] + a[right];
if (sum == target) return new int[] { left, right };
// 数组有序:和偏小时,只有增大左值才可能接近目标。
if (sum < target) left++;
else right--;
}
return new int[] { -1, -1 };
}
static int removeDuplicates(int[] sorted) {
if (sorted.length == 0) return 0;
// 区间 [0, slow) 始终保存已经去重的结果。
int slow = 1;
for (int fast = 1; fast < sorted.length; fast++) {
// fast 扫描输入,遇到新值时写入结果区末尾。
if (sorted[fast] != sorted[slow - 1]) sorted[slow++] = sorted[fast];
}
return slow;
}
static int longestUnique(String text) {
Map<Integer, Integer> last = new HashMap<>();
int[] codePoints = text.codePoints().toArray();
int left = 0,
best = 0;
for (int right = 0; right < codePoints.length; right++) {
// put 返回当前字符上一次出现的位置。
Integer previous = last.put(codePoints[right], right);
// 上次位置仍在窗口内才收缩;left 绝不能向左回退。
if (previous != null && previous >= left) left = previous + 1;
// 此时 [left, right] 已恢复为无重复窗口。
best = Math.max(best, right - left + 1);
}
return best;
}
// 运行入口:使用一组包含典型边界的数据验证主要算法。
public static void main(String[] args) {
System.out.println(
Arrays.toString(twoSumSorted(new int[] { 1, 2, 4, 7, 11 }, 9))
);
int[] values = { 1, 1, 2, 2, 3 };
int length = removeDuplicates(values);
System.out.println(Arrays.toString(Arrays.copyOf(values, length)));
System.out.println(longestUnique("abca😀b"));
}
}手工推演:abba
读到第二个 b 时,上次位置 1 仍在窗口内,left 跳到 2;最后读到 a 时,它上次位于 0,已经在窗口外,不能让 left 回退。最终最长长度为 2。
对 main 手工推导,预期依次输出 [1, 3]、[1, 2, 3]、4,这些不是实际运行记录。第一组下标对应 2 + 7 = 9;第三项按码点计算,无重复子串 ca😀b 的长度为 4。
7. 不适合直接使用窗口的情况
- 无序数组上依赖大小关系,却没有可安全淘汰候选的单调性;
- 数组含负数,使“扩大窗口只增大区间和”不再成立;
- 删除左端元素后无法增量恢复状态;
- 目标依赖窗口外历史或需要任意位置回退;
- 字符串索引按 UTF-16
char,业务却要求 Unicode Code Point 或用户感知字符。
例如数组 [1, -1, 5],目标 K = 5。按第 3 节的普通最短窗口流程,右端扩展到最后时和为 5,记录长度 3;移除左端的 1 后和为 4,便停止收缩。这样会漏掉长度为 1 的 [5],因为继续移除负数反而能增大和。
这类问题通常使用前缀和与单调队列。前缀和保存从开头到每个位置之前的累计值,两个前缀和相减就得到区间和;单调队列让候选起点对应的前缀和保持有序,并排除不可能更优的候选。单调队列的基本模型见前置链接中的栈与队列文章。负数破坏的是这里对区间和的单调性,并不表示含负数的所有问题都不能使用窗口。
8. 验证清单
下面是建议执行的检查:
- 空输入、单元素、全部重复、全部不同;
- 最优窗口位于开头、末尾或覆盖全部输入;
left连续移动多次后仍不回退;- 若用计数表维护窗口,重复元素离开时减少对应计数;若用本文的最近位置表,窗口外记录不能使
left回退; - 对字符串窗口,与逐个起点向右扫描、遇到重复就停止的
O(n²)小规模基线做差分测试,即用同一输入比较两种实现的结果;两者必须使用相同的字符计数单位; - 链表覆盖无环、自环、环入口在头部和中间的情况;有序两数之和覆盖无解、重复值以及两个
int相加会溢出的边界; - 原地去重检查返回长度及有效前缀,而不是要求整个数组都被清空或压缩。
9. 容易踩的坑
- 混用闭区间与左闭右开区间的长度公式。本文字符串窗口用
[left, right],去重结果区用[0, slow)。 - 在
abba的最后一个a处,把窗口外的旧位置当作有效位置,让left回退到 1,窗口重新出现重复字符。 - 无序数据使用相向指针后错误淘汰候选。
- 固定窗口更新答案前没有恢复指定长度,或求最短满足窗口时尚未满足条件就记录答案。
10. 总结
减少重复扫描的关键,是证明哪些位置无需再考虑,并控制指针移动和状态更新的总成本。
- 有序性让相向指针可以安全淘汰一侧候选。
- 滑动窗口要求状态能随左右边界增量维护。
- 快慢指针需要说明读写区域为何安全,或不同速度为何保证在环内相遇;它与窗口使用不同的正确性依据。