同向双指针统一视角：快慢指针与滑动窗口的辩证关系

摘要

“双指针”和”滑动窗口”在很多教程中被分开讲，但它们本质上是同一套思想的不同侧面——都是通过两个指针限定一段连续区间，利用单调性将 $O (n^{2})$ 枚举降到 $O (n)$ 。本文从”同向双指针”的统一视角出发，厘清三种形态（快慢指针、缩减型双指针、滑动窗口）之间的语义差异与适用边界，并通过 LeetCode 209（长度最小的子数组）、LeetCode 904（水果成篮）、LeetCode 2401（最长优美子数组）三道题，演示如何用统一的思维框架驾驭这一类问题。

第 1 章双指针的分类与本质

1.1 双指针不是一种算法，而是一类技法

“双指针”是算法题中一个宽泛的技法类别，而不是某个具体的算法。根据两个指针的相对位置和移动方向，可以分为：

对向双指针（Two Pointers）：left 从左往右，right 从右往左，两者相向而行。典型应用：有序数组中的两数之和、三数之和的内层收缩。

同向双指针（Fast-Slow Pointers）：left 和 right 都从左往右，right 走得更快或更远。分两种子形态：

快慢指针（Floyd 判圈算法、链表中点、链表倒数 k 节点）：fast 和 slow 步长不同，目的是利用相对速度差达到某种几何效果
滑动窗口：left 和 right 共同界定一个连续区间 $[l e f t, r i g h t]$ ，目的是高效枚举所有合法子区间

本篇的重点是同向双指针，特别是它与滑动窗口的关系。

1.2 同向双指针的核心假设

同向双指针（滑动窗口）能正确工作的根本条件是单调性：

对于固定的 right，当 left 从小到大增加时，区间 $[l e f t, r i g h t]$ 的某个属性（合法性、代价等）是单调变化的。

这意味着：对于给定的 right，满足”区间合法”的 left 存在一个分界点——所有小于该分界点的 left 都使区间不合法（区间太大），所有大于等于该分界点的 left 都使区间合法（区间够小）。这个分界点随着 right 的增大而单调不减，因此两个指针都只需要向右移动，总复杂度 $O (n)$ 。

核心概念：单调性是复杂度降低的根本

如果没有单调性，每次 right 移动后，left 的最佳位置可能在任意地方，需要全局搜索，回退到 $O (n^{2})$ 。正是单调性保证了 left 只向右走，不回头，从而实现 $O (n)$ 。

1.3 快慢指针与滑动窗口的语义差异

维度	快慢指针	滑动窗口
应用场景	链表（有环检测、找中点、倒数 k 节点）	数组/字符串（连续子区间）
指针含义	`fast` 和 `slow` 表示两个独立的游走位置，无区间语义	`left` 和 `right` 共同界定区间 $[l e f t, r i g h t]$
移动策略	`fast` 每次走 2 步，`slow` 走 1 步（或类似的固定比例）	`right` 持续扩展，`left` 按需收缩
目标	利用相对速度检测几何性质（环、中点）	高效枚举所有合法子区间

尽管名字不同，两者都只向前走，不回头，共享 $O (n)$ 的复杂度来源。

第 2 章 LeetCode 209：长度最小的子数组

2.1 题目

LeetCode 209 - Minimum Size Subarray Sum（中等）

给定一个含有 $n$ 个正整数的数组和一个正整数 target，找出该数组中满足其总和大于等于 target 的长度最小的连续子数组，并返回其长度；如果不存在符合条件的子数组，返回 0。

输入：target = 7, nums = [2,3,1,2,4,3]
输出：2，解释：子数组 [4,3] 是该条件下的长度最小的子数组

输入：target = 4, nums = [1,4,4]
输出：1

输入：target = 11, nums = [1,1,1,1,1,1,1,1]
输出：0，没有子数组满足条件

约束：所有元素都是正整数（这是关键！）

2.2 为什么正整数约束至关重要

如果数组中有负数，“子数组和 ≥ target”就没有单调性了——在子数组中加入一个负数，和反而减小；去掉一个正数，和可能还满足条件。单调性被打破，滑动窗口不适用。

但题目保证了正整数，因此：

右指针扩展（加入正整数），子数组和只会增大
左指针收缩（去掉正整数），子数组和只会减小

这给了子数组和关于区间大小的单调性，滑动窗口可以正确工作。

2.3 滑动窗口解法

这是一道”求最短合法窗口”的可变窗口题，框架与 LeetCode 76 相同：while(合法) 时收缩，收缩前更新答案。

public int minSubArrayLen(int target, int[] nums) {
    int n = nums.length;
    int left = 0, sum = 0;
    int minLen = Integer.MAX_VALUE;
 
    for (int right = 0; right < n; right++) {
        sum += nums[right];  // 进窗
 
        // 当窗口合法时（sum >= target），记录答案并收缩
        while (sum >= target) {
            minLen = Math.min(minLen, right - left + 1);
            sum -= nums[left++];  // 出窗
        }
    }
 
    return minLen == Integer.MAX_VALUE ? 0 : minLen;
}

时间复杂度： $O (n)$ 空间复杂度： $O (1)$

2.4 与 LeetCode 76 的对比

LeetCode 209 和 LeetCode 76 都是”求最短合法窗口”，代码结构几乎相同：

// LeetCode 76：最小覆盖子串
while (formed == required) {
    update answer;
    remove(left++);
}
 
// LeetCode 209：最小子数组和
while (sum >= target) {
    update answer;
    sum -= nums[left++];
}

区别只在于”合法条件”的定义不同。这印证了第 01 篇提到的：滑动窗口是一个框架，“合法条件”是往框架里填充的内容，不同题目填不同内容。

2.5 $O (n lo g n)$ 解法：前缀和 + 二分（扩展）

题目还要求给出一个 $O (n lo g n)$ 的进阶解法。可以用前缀和 + 二分查找：

public int minSubArrayLen(int target, int[] nums) {
    int n = nums.length;
    int[] prefix = new int[n + 1];
    for (int i = 0; i < n; i++) prefix[i + 1] = prefix[i] + nums[i];
 
    int minLen = Integer.MAX_VALUE;
    for (int left = 0; left < n; left++) {
        // 找最小的 right 使得 prefix[right+1] - prefix[left] >= target
        // 即 prefix[right+1] >= prefix[left] + target
        int need = prefix[left] + target;
        // 在 prefix[left+1..n] 中二分找第一个 >= need 的位置
        int lo = left + 1, hi = n;
        while (lo < hi) {
            int mid = (lo + hi) / 2;
            if (prefix[mid] >= need) hi = mid;
            else lo = mid + 1;
        }
        if (lo <= n && prefix[lo] >= need) {
            minLen = Math.min(minLen, lo - left);
        }
    }
    return minLen == Integer.MAX_VALUE ? 0 : minLen;
}

这是前缀和（第 08 篇）与二分查找的结合， $O (n lo g n)$ 比滑动窗口的 $O (n)$ 慢，但展示了”多种思路求解同一题”的思维灵活性。

第 3 章 LeetCode 904：水果成篮

3.1 题目

LeetCode 904 - Fruit Into Baskets（中等）

你有两个篮子，每个篮子只能放一种类型的水果。给定一个整数数组 fruits，找出能放进篮子的最多水果数目（必须从连续的树上采，且采摘过程中篮子不能超出类型限制）。

等价描述：找最长的子数组，使得子数组中不同整数的种类数不超过 2。

输入：fruits = [1,2,1]
输出：3（整个数组，含 {1,2} 两种，合法）

输入：fruits = [0,1,2,2]
输出：3（子数组 [1,2,2] 或 [0,1,2]，含两种水果）

输入：fruits = [1,2,3,2,2]
输出：4（子数组 [2,3,2,2]，含 {2,3} 两种）

3.2 问题本质：至多 k 种不同元素的最长子数组（k=2）

这道题的实质是”最多 2 种不同元素的最长子数组”，是”最多 k 种不同元素的最长子数组”的特化版（k=2）。

窗口合法条件：窗口内不同数字的种类数 ≤ 2（或通用版：≤ k）。

维护”不同种类数”的方法：用哈希表（或数组）记录窗口内每种元素的频率，size() 就是当前种类数。当某种元素频率降为 0 时，从哈希表中移除，种类数减 1。

public int totalFruit(int[] fruits) {
    int left = 0, maxLen = 0;
    Map<Integer, Integer> freq = new HashMap<>();
 
    for (int right = 0; right < fruits.length; right++) {
        // 进窗
        freq.merge(fruits[right], 1, Integer::sum);
 
        // 收缩：种类数超过 2 时
        while (freq.size() > 2) {
            int out = fruits[left++];
            freq.merge(out, -1, Integer::sum);
            if (freq.get(out) == 0) freq.remove(out);  // 频率为 0，移除
        }
 
        maxLen = Math.max(maxLen, right - left + 1);
    }
    return maxLen;
}

时间复杂度： $O (n)$ （每个元素进出各一次，哈希操作均摊 $O (1)$ ） 空间复杂度： $O (k)$ （哈希表中至多 $k + 1$ 个元素）

3.3 通用化：至多 k 种不同元素的最长子数组

904 的代码只需把 > 2 改为 > k 就变成了通用解法：

public int longestSubarrayWithKDistinct(int[] nums, int k) {
    int left = 0, maxLen = 0;
    Map<Integer, Integer> freq = new HashMap<>();
 
    for (int right = 0; right < nums.length; right++) {
        freq.merge(nums[right], 1, Integer::sum);
 
        while (freq.size() > k) {
            int out = nums[left++];
            freq.merge(out, -1, Integer::sum);
            if (freq.get(out) == 0) freq.remove(out);
        }
 
        maxLen = Math.max(maxLen, right - left + 1);
    }
    return maxLen;
}

这个通用框架可以解决一大类”至多 k 种”的问题，包括 LeetCode 340（至多 k 个不同字符的最长子串）、LeetCode 992（恰好 k 个不同整数的子数组，详见第 09 篇）等。

3.4 哈希表 vs 数组：何时选哪种

场景	推荐数据结构	理由
字符集固定（如 26 个字母）	`int[26]` 数组	访问 $O (1)$ ，无装箱，代码简洁
字符集是全 ASCII	`int[128]` 数组	空间可接受，比 HashMap 快
元素范围大但种类有限	`HashMap<Integer, Integer>`	不知道值域大小时的安全选择
元素是对象或字符串	`HashMap`	无法用数组索引

LeetCode 904 中，fruits[i] 可以是任意整数（ $0 \leq f r u i t s [i] < f r u i t s . l e n g t h$ ，范围可达 $1 0^{5}$ ），用数组大小为 $1 0^{5}$ 不合适，因此用 HashMap。

第 4 章 LeetCode 2401：最长优美子数组

4.1 题目

LeetCode 2401 - Longest Nice Subarray（中等）

如果一个子数组中，任意两个不同下标的元素按位与（&）的结果都等于 0，则称该子数组为优美子数组。找出最长优美子数组的长度。

输入：nums = [1,3,8,48,10]
输出：3，解释：子数组 [3,8,48] 满足：3&8=0, 3&48=0, 8&48=0（任意两元素不共享位）

输入：nums = [3,1,5,11,13]
输出：1，解释：任意长度 > 1 的子数组都有两个元素共享某一 bit

4.2 “按位与为 0”的集合语义

“任意两个元素按位与为 0”意味着：这两个元素在二进制表示上，没有任何一位同时为 1。换句话说，它们的二进制 1 的集合是不相交的。

将整个子数组看作一个整体：子数组内所有元素的二进制 1 的集合，两两不相交。这等价于：

窗口内所有元素的按位或（|）的结果，等于窗口内所有元素按位或的理论最大值——也就是说，所有 bit 至多被一个元素占用。

更简洁地表达：窗口内任意两个元素共享的 bit 数为 0。

用一个聚合量来表示窗口状态：usedBits = 窗口内所有元素的按位或。“合法”条件是：(usedBits & nums[right]) == 0（新加入的元素与已有元素不共享任何 bit）。

4.3 合法性的单调性验证

进窗：加入 nums[right]，usedBits |= nums[right]，如果 nums[right] 与已有 bit 不冲突，窗口合法
出窗：能否简单地 usedBits &= ~nums[left]？

注意：usedBits 是按位或，“撤销”（removing a bit）需要确认该 bit 不被其他元素持有。如果多个元素都有某个 bit，去掉一个元素不能简单地把该 bit 清零。

解决方案：每次出窗时，重新计算 usedBits（从 left+1 到 right 的按位或）——但这需要 $O (n)$ 时间，退化到 $O (n^{2})$ 。

更好的方案：因为”合法”要求任意两元素不共享 bit，窗口合法意味着所有元素的 bit 两两不交，因此 usedBits = nums[left] | nums[left+1] | ... | nums[right]，每个 bit 至多由一个元素持有。出窗时，nums[left] 独占它的所有 bit，可以安全地 usedBits ^= nums[left]（异或，等价于清除独占的 bit）。

public int longestNiceSubarray(int[] nums) {
    int n = nums.length;
    int left = 0, usedBits = 0, maxLen = 0;
 
    for (int right = 0; right < n; right++) {
        // 收缩：若 nums[right] 与已有 bit 冲突，先出窗
        while ((usedBits & nums[right]) != 0) {
            usedBits ^= nums[left];  // 清除 left 元素独占的 bit
            left++;
        }
        // 进窗
        usedBits |= nums[right];
        maxLen = Math.max(maxLen, right - left + 1);
    }
    return maxLen;
}

时间复杂度： $O (n)$ ，均摊 空间复杂度： $O (1)$

4.4 为什么 `usedBits ^= nums[left]` 是安全的

安全性依赖”窗口合法时，任意两元素不共享 bit”。这意味着 usedBits 中的每个 1 bit，恰好对应窗口内的某个元素的某个 1 bit，且各元素不重叠。所以 nums[left] 的每个 bit，只在 usedBits 中出现一次，XOR 可以精确地将其清除。

生产避坑：XOR 撤销的前提

usedBits ^= x 能正确”撤销” x 的贡献，仅当 x 的每个 bit 在 usedBits 中出现奇数次（通常是恰好 1 次）时才成立。如果多个元素共享某个 bit，XOR 撤销会出错。本题的”优美”条件保证了这个前提——这是 XOR 能用于状态撤销的充要条件。

第 5 章统一框架回顾与选型指南

5.1 三题共性：单调性驱动同向移动

题目	合法条件	状态	出窗操作
209 最小子数组和	sum >= target	sum（整数）	sum -= nums[left]
904 水果成篮	freq.size() ⇐ 2	freq（HashMap）	freq.get(left)—, 若 0 则 remove
2401 最长优美子数组	(usedBits & new) == 0	usedBits（位掩码）	usedBits ^= nums[left]

三道题的框架完全一致，差别只在于”窗口状态”的数据结构和”合法条件”的判断逻辑。这印证了：学滑动窗口，核心是学”窗口状态的设计”，框架本身是固定的。

5.2 什么时候用同向双指针（滑动窗口），什么时候用对向双指针

**同向双指针（滑动窗口）**的适用信号：

目标是连续子数组/子字符串（而不是任意两个元素的组合）
问题有单调性（区间越大越”宽松”或越”紧”）
求最长/最短合法子区间，或统计合法子区间数

对向双指针的适用信号：

数组已排序（或可以排序）
寻找两个元素的组合满足某个条件（如两数之和等于 target）
题目涉及”两端收缩”（如装最多水的容器 LeetCode 11）

5.3 同向双指针与 BFS/DFS 的边界

有些图遍历问题也用双指针（如二分图的快慢指针判圈），这些是快慢指针在图上的应用，与本专栏的子数组窗口场景不同。区分的方式：如果数据结构是数组/字符串，且目标是连续子区间，几乎一定是滑动窗口；如果数据结构是链表/图，才考虑快慢指针或 Floyd 算法。

本篇总结

本篇以”同向双指针统一视角”为线索，串联了快慢指针和滑动窗口的语义差异，并通过三道题展示了滑动窗口窗口状态的多样性：

LeetCode 209：最简单的整数求和窗口，“最短合法窗口”框架
LeetCode 904：哈希表维护”种类数”，“至多 k 种不同元素”的通用模式
LeetCode 2401：位掩码维护”bit 占用集合”，XOR 撤销的精妙应用

核心洞见：滑动窗口的威力来源于单调性——不论窗口状态是整数、哈希表还是位掩码，只要状态关于区间大小有单调性，两个指针就能各走一遍， $O (n)$ 解决问题。

参考与延伸

01 滑动窗口算法原理全景：从暴力枚举到 O(n) 的思维跃迁 — 单调性的理论基础
09 多类别元素与恰好 K 型窗口：高阶滑动窗口技法 — “至多 k 种”的进阶变体
08 前缀和与滑动窗口的思想融合：子数组求和类问题 — 209 的 O(nlogn) 解法详解

课后练习

LeetCode 1208 - 尽可能使字符串相等（中等）

给你两个长度相同的字符串 s 和 t，每次操作可以将 s[i] 变为字符串中任意字符，代价为 |s[i] - t[i]|。预算为 maxCost，求可以转化的最长连续子串。

提示：先构建差值数组 diff[i] = |s.charAt(i) - t.charAt(i)|，问题转化为「差值数组中，和不超过 maxCost 的最长子数组」——全非负数 + 不超过某值，标准可变窗口最长模板（与 LeetCode 209 同构）。

汀的知识碎片

文章导航

05 同向双指针统一视角：快慢指针与滑动窗口的辩证关系

同向双指针统一视角：快慢指针与滑动窗口的辩证关系

摘要

第 1 章双指针的分类与本质

1.1 双指针不是一种算法，而是一类技法

1.2 同向双指针的核心假设

1.3 快慢指针与滑动窗口的语义差异

第 2 章 LeetCode 209：长度最小的子数组

2.1 题目

2.2 为什么正整数约束至关重要

2.3 滑动窗口解法

2.4 与 LeetCode 76 的对比

2.5 $O (n lo g n)$ 解法：前缀和 + 二分（扩展）

第 3 章 LeetCode 904：水果成篮

3.1 题目

3.2 问题本质：至多 k 种不同元素的最长子数组（k=2）

3.3 通用化：至多 k 种不同元素的最长子数组

3.4 哈希表 vs 数组：何时选哪种

第 4 章 LeetCode 2401：最长优美子数组

4.1 题目

4.2 “按位与为 0”的集合语义

4.3 合法性的单调性验证

4.4 为什么 `usedBits ^= nums[left]` 是安全的

第 5 章统一框架回顾与选型指南

5.1 三题共性：单调性驱动同向移动

5.2 什么时候用同向双指针（滑动窗口），什么时候用对向双指针

5.3 同向双指针与 BFS/DFS 的边界

本篇总结

参考与延伸

课后练习

On this page

Backlinks

汀的知识碎片

文章导航

05 同向双指针统一视角：快慢指针与滑动窗口的辩证关系

同向双指针统一视角：快慢指针与滑动窗口的辩证关系

摘要

第 1 章 双指针的分类与本质

1.1 双指针不是一种算法，而是一类技法

1.2 同向双指针的核心假设

1.3 快慢指针与滑动窗口的语义差异

第 2 章 LeetCode 209：长度最小的子数组

2.1 题目

2.2 为什么正整数约束至关重要

2.3 滑动窗口解法

2.4 与 LeetCode 76 的对比

2.5 O(nlogn) 解法：前缀和 + 二分（扩展）

第 3 章 LeetCode 904：水果成篮

3.1 题目

3.2 问题本质：至多 k 种不同元素的最长子数组（k=2）

3.3 通用化：至多 k 种不同元素的最长子数组

3.4 哈希表 vs 数组：何时选哪种

第 4 章 LeetCode 2401：最长优美子数组

4.1 题目

4.2 “按位与为 0”的集合语义

4.3 合法性的单调性验证

4.4 为什么 usedBits ^= nums[left] 是安全的

第 5 章 统一框架回顾与选型指南

5.1 三题共性：单调性驱动同向移动

5.2 什么时候用同向双指针（滑动窗口），什么时候用对向双指针

5.3 同向双指针与 BFS/DFS 的边界

本篇总结

参考与延伸

课后练习

On this page

Backlinks

第 1 章双指针的分类与本质

2.5 $O (n lo g n)$ 解法：前缀和 + 二分（扩展）

4.4 为什么 `usedBits ^= nums[left]` 是安全的

第 5 章统一框架回顾与选型指南