双指针与滑动窗口
02-高级算法2026/11/14
双指针把两两枚举压成单向扫描，滑动窗口是它在连续区间上的特化，指针总移动次数仍是 O(n)。
前端做字符串 diff 时要同步扫描两份文本，排查线上问题时要在日志里找一段连续时间满足错误率阈值。这两类需求都不需要回头看，指针只朝一个方向走，天然适合双指针与滑动窗口。
三种形态
| 形态 | 指针方向 | 典型题 | 关键点 |
|---|---|---|---|
| 同向快慢 | 都向右，速度不同 | 判环、删除重复、移动零 | slow 写、fast 读 |
| 相向对撞 | 一个从左、一个从右 | 两数之和 II、三数之和、盛水、反转 | 移动哪侧由单调性决定 |
| 分离双指针 | 各自在自己的序列上前进 | 合并两个有序数组、链表相交 | 两条链互不干扰 |
快慢指针不要求有序，对撞指针才依赖单调性：数组有序时，左指针右移会让和变大，右指针左移会让和变小，才能确定该动哪一边。
快慢指针判环
Floyd 判圈算法让 slow 每次走一步、fast 每次走两步。slow 进环后，fast 已经在环内，两者距离每轮缩小 1，所以一定会相遇，不会因为相对速度大于 1 而跳过。
function hasCycle(head) {
let slow = head, fast = head;
while (fast && fast.next) {
slow = slow.next;
fast = fast.next.next;
if (slow === fast) return true;
}
return false;
}
找环入口时，相遇后把其中一个指针放回 head，两者同速前进，再次相遇的位置就是入口。设 head 到入口距离 a、入口到相遇点 b、环长 b+c，则 2(a+b) = a+b+n(b+c)，化简得 a = c + (n-1)(b+c)，所以从 head 走 a 步与从相遇点走 c 步会同时到达入口。
function detectCycle(head) {
let slow = head, fast = head;
while (fast && fast.next) {
slow = slow.next;
fast = fast.next.next;
if (slow === fast) {
let p = head;
while (p !== slow) { p = p.next; slow = slow.next; }
return p;
}
}
return null;
}
滑动窗口的条件与模板
适用条件是"连续子数组或子串"加"单调性"：窗口右扩时指标单调变化，左缩时能恢复。求最长用 while (不满足) 收缩，求最短用 while (满足) 收缩，两个循环都只在指针移动时执行，总复杂度 O(n)。
function slidingWindow(s) {
let left = 0, ans = 0;
const window = new Map();
for (let right = 0; right < s.length; right++) {
扩张(window, s[right]);
while (不满足条件(window)) {
收缩(window, s[left]);
left++;
}
更新答案(ans, right - left + 1);
}
return ans;
}
定长窗口与不定长窗口的区别在收缩时机：定长窗口大小固定为 k，右指针每走一步，左指针固定跟到 right - k + 1，用 if 减掉离开的元素即可；不定长窗口要靠 while 反复收缩，直到条件重新满足。
// 定长窗口：长度为 k 的子数组最大和
function maxSumWindow(nums, k) {
let sum = 0, ans = 0;
for (let right = 0; right < nums.length; right++) {
sum += nums[right];
if (right >= k) sum -= nums[right - k];
if (right >= k - 1) ans = Math.max(ans, sum);
}
return ans;
}
为什么用 Map 而不是每次重算
如果每移动一次右指针都把窗口内元素重新统计一遍，单次是 O(k)，整体退化成 O(nk)。用 Map 或计数数组增量维护，进入窗口加一、离开窗口减一，每次移动 O(1)。ASCII 字符可以用长度 128 的数组，Unicode 字符必须用 Map。