数组与双指针 / 滑动窗口
双指针和滑动窗口是数组/字符串题型中最高频的技巧，覆盖 LeetCode 中至少 30% 的中等题目。掌握这两个模式，可以将暴力 O(n²) 解法优化到 O(n)，是面试中展示算法思维的最佳切入点。
一、双指针技巧
双指针的核心思想是：用两个下标（指针）同时扫描数组，利用有序性或某种单调性跳过不必要的枚举，从而将两层循环压缩到一层。
根据两个指针的运动方向，分为两大类：
| 类型 | 指针方向 | 适用场景 |
|---|---|---|
| 对撞指针 | 相向运动（一左一右） | 有序数组、容积问题、回文判断 |
| 快慢指针 | 同向运动（速度不同） | 链表环检测、原地删除、中间节点 |
1.1 对撞指针（左右指针）
思路：在已排序数组两端分别放置左指针 L 和右指针 R，每次根据当前两值之和与目标的关系决定哪侧收缩。
sum < target→ 左指针右移（增大）sum > target→ 右指针左移（减小）sum == target→ 找到答案
对撞指针流程图
典型题：LC 167 两数之和 II（有序数组）
题目：给定一个升序整数数组 numbers，找两个数使其和等于 target，返回下标（1-based）。
执行过程演示
Java 完整代码：
class Solution {
public int[] twoSum(int[] numbers, int target) {
int left = 0, right = numbers.length - 1;
while (left < right) {
int sum = numbers[left] + numbers[right];
if (sum == target) {
// 题目要求 1-based 下标
return new int[]{left + 1, right + 1};
} else if (sum < target) {
left++; // 和太小，左指针右移增大
} else {
right--; // 和太大，右指针左移减小
}
}
return new int[]{-1, -1}; // 题目保证有解，实际不会到此
}
}复杂度：时间 O(n)，空间 O(1)
1.2 快慢指针
思路：两个指针从同一起点出发，一个每次走 1 步（慢指针），一个每次走 2 步（快指针）。
- 环检测：快指针若在环内会追上慢指针
- 原地去重：慢指针维护"有效区间"末尾，快指针扫描
快慢指针流程图
典型题：LC 26 删除有序数组中的重复项
题目：原地删除升序数组 nums 中的重复元素，返回新长度 k，前 k 个元素不重复。
数组 [1, 1, 2, 3, 3]，slow（紫）维护有效区末尾，fast（橙）向前扫描：
fast=1：nums[fast]=1 == nums[slow]=1，重复，fast++跳过fast=2：nums[fast]=2 != nums[slow]=1，不重复，slow++，写入 2fast=3：nums[fast]=3 != nums[slow]=2，不重复，slow++，写入 3fast=4：nums[fast]=3 == nums[slow]=3，重复，fast++跳过；返回slow+1=3
Java 完整代码：
class Solution {
public int removeDuplicates(int[] nums) {
if (nums.length == 0) return 0;
int slow = 0; // slow 维护不重复区间的末尾
for (int fast = 1; fast < nums.length; fast++) {
if (nums[fast] != nums[slow]) {
// 发现新元素，slow 右移并写入
slow++;
nums[slow] = nums[fast];
}
// nums[fast] == nums[slow] 时，fast 直接跳过（重复元素）
}
return slow + 1; // 不重复元素个数
}
}复杂度：时间 O(n)，空间 O(1)
二、滑动窗口
滑动窗口是双指针的延伸：维护一段连续区间 [left, right]，通过右扩和左缩的方式在 O(n) 时间内解决子数组/子串问题。
初始：left=0, right=0
↓
[L....R] → 窗口向右滑动根据窗口大小是否固定，分为两类：
| 类型 | 特征 | 典型题 |
|---|---|---|
| 固定窗口 | 窗口大小 k 不变 | LC 643 子数组最大平均值 |
| 可变窗口 | 动态扩缩满足条件 | LC 3、LC 76、LC 209 |
2.1 固定大小窗口
框架：先建立大小为 k 的初始窗口，然后每次右移一格（加入右侧新元素，移出左侧旧元素）。
2.2 可变大小窗口
核心思路：
right不断向右扩展，将新元素纳入窗口- 当窗口不满足条件时，
left向右收缩直到恢复合法 - 每步更新最优解
三、经典题目深度解析
LC 11 盛最多水的容器
题目：给定 n 个非负整数 height[i]，第 i 条竖线的高度为 height[i]，找出两条线使其与 x 轴构成容器能容纳最多的水。
思路分析：容积 = min(height[L], height[R]) × (R - L)。
关键结论：移动较短边，才有可能增大容积（移动较长边，宽度减小，高度上限不变，容积只会减小或不变）。
LC 11 流程图
执行过程演示
数组 height = [1, 8, 6, 2, 5, 4, 8, 3, 7]，共 9 个柱子：
Java 完整代码：
class Solution {
public int maxArea(int[] height) {
int left = 0, right = height.length - 1;
int maxWater = 0;
while (left < right) {
// 计算当前容积：宽度 × 较短边高度
int water = Math.min(height[left], height[right]) * (right - left);
maxWater = Math.max(maxWater, water);
// 移动较短边（移动较长边只会让容积减小）
if (height[left] < height[right]) {
left++;
} else {
right--;
}
}
return maxWater;
}
}复杂度：时间 O(n)，空间 O(1)
进阶：LC 42 接雨水（每格独立计算，需要 prefix max）
LC 3 无重复字符的最长子串
题目：给定字符串 s，找出其中不含重复字符的最长子串的长度。
思路：可变滑动窗口，用 HashMap 记录每个字符最近一次出现的位置。当 right 遇到已在窗口内的字符，将 left 跳到该字符上次出现位置的下一位。
LC 3 流程图
执行过程演示
字符串 s = "abcabcbb"，拆成单字符数组，橙色（current）表示窗口范围，黄色（active）表示当前处理字符：
Java 完整代码：
class Solution {
public int lengthOfLongestSubstring(String s) {
// map 记录字符最近一次出现的下标
Map<Character, Integer> map = new HashMap<>();
int maxLen = 0;
int left = 0;
for (int right = 0; right < s.length(); right++) {
char c = s.charAt(right);
// 若字符已在窗口内，将 left 跳到重复字符的下一个位置
if (map.containsKey(c) && map.get(c) >= left) {
left = map.get(c) + 1;
}
// 更新字符的最新位置
map.put(c, right);
// 更新最大窗口长度
maxLen = Math.max(maxLen, right - left + 1);
}
return maxLen;
}
}复杂度：时间 O(n)，空间 O(min(m,n))，m 为字符集大小
LC 15 三数之和
题目：给定整数数组 nums，找出所有满足 nums[i] + nums[j] + nums[k] == 0 且 i < j < k 的不重复三元组。
思路：排序后固定第一个数 nums[i]，在 [i+1, n-1] 范围内用对撞指针找另外两个数。去重是本题难点。
LC 15 流程图
步骤可视化
数组 [-4, -1, -1, 0, 1, 2]（已排序）：
-4 + (-1) + 2 = -3 < 0，sum 偏小，L++
-4 + (-1) + 2 = -3 < 0，仍然偏小，L++，最终 L 超过 R，i=0 无解
-1 + 0 + 1 = 0，命中！记录 [-1, 0, 1]，两指针内收同时跳过重复
nums[2] == nums[1] == -1，重复，continue 跳过，避免产生重复三元组
i=3，nums[3]=0，L=4，R=5：0 + 1 + 2 = 3 > 0，R--
R 超过 L，此 i 无解。最终结果：[[-1, 0, 1], [-1, -1, 2]]
等等，让我们补全 i=3 的完整步骤：
当 L=4, R=5：0+1+2=3>0，R-- → R=4，L=R，退出。i=3 无解。
但 i=1 时还有另一组：L=2(-1), R=5(2) 时：-1+(-1)+2=0，命中！记录 [-1,-1,2]
Java 完整代码：
class Solution {
public List<List<Integer>> threeSum(int[] nums) {
List<List<Integer>> result = new ArrayList<>();
Arrays.sort(nums); // 排序，使对撞指针有效
int n = nums.length;
for (int i = 0; i < n - 2; i++) {
// 最小值已大于 0，后续不可能有解
if (nums[i] > 0) break;
// 跳过重复的 i，避免重复三元组
if (i > 0 && nums[i] == nums[i - 1]) continue;
int left = i + 1, right = n - 1;
while (left < right) {
int sum = nums[i] + nums[left] + nums[right];
if (sum == 0) {
result.add(Arrays.asList(nums[i], nums[left], nums[right]));
// 跳过重复的 left
while (left < right && nums[left] == nums[left + 1]) left++;
// 跳过重复的 right
while (left < right && nums[right] == nums[right - 1]) right--;
left++;
right--;
} else if (sum < 0) {
left++;
} else {
right--;
}
}
}
return result;
}
}复杂度：时间 O(n²)，空间 O(1)（排除结果空间）
进阶：LC 18 四数之和（再加一层循环，同样去重）
LC 42 接雨水
题目：给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。
思路（双指针）：每格能接的雨水 = min(左侧最大高度, 右侧最大高度) - 自身高度。
用双指针维护 leftMax 和 rightMax：
- 若
leftMax <= rightMax，则左侧是短板，处理左指针 - 否则右侧是短板，处理右指针
LC 42 流程图
执行过程演示
数组 height = [0,1,0,2,1,0,1,3,2,1,2,1]，蓝色为左指针（L），红色为右指针（R），橙色为当前计算积水格，青色为已处理格：
Java 完整代码：
class Solution {
public int trap(int[] height) {
int left = 0, right = height.length - 1;
int leftMax = 0, rightMax = 0;
int result = 0;
while (left <= right) {
if (height[left] <= height[right]) {
if (height[left] >= leftMax) {
leftMax = height[left]; // 更新左侧最大值
} else {
result += leftMax - height[left]; // 当前格可积水
}
left++;
} else {
if (height[right] >= rightMax) {
rightMax = height[right]; // 更新右侧最大值
} else {
result += rightMax - height[right]; // 当前格可积水
}
right--;
}
}
return result;
}
}复杂度：时间 O(n)，空间 O(1)
进阶：单调栈解法可以计算出每一段积水的具体宽度
LC 1 两数之和
题目：给定整数数组 nums 和目标值 target，找出和为 target 的两个整数的下标（数组无序）。
思路：哈希表一遍扫描。遍历到 nums[i] 时，检查 target - nums[i] 是否已在哈希表中。
LC 1 流程图
数组 [2, 7, 11, 15]，target = 9
| i | nums[i] | target - nums[i] | map 中存在？ | 操作 |
|---|---|---|---|---|
| 0 | 2 | 7 | 否 | map.put(2, 0) |
| 1 | 7 | 2 | 是！map[2]=0 | 返回 [0, 1] |
Java 完整代码：
class Solution {
public int[] twoSum(int[] nums, int target) {
// key: 数值, value: 下标
Map<Integer, Integer> map = new HashMap<>();
for (int i = 0; i < nums.length; i++) {
int complement = target - nums[i];
if (map.containsKey(complement)) {
// 找到了互补的数
return new int[]{map.get(complement), i};
}
map.put(nums[i], i);
}
return new int[]{-1, -1}; // 题目保证有解
}
}复杂度：时间 O(n)，空间 O(n)
四、题型总结与通用模板
4.1 对撞指针模板
// 适用条件：有序数组，利用单调性收缩
int left = 0, right = nums.length - 1;
while (left < right) {
// 根据当前值计算某个指标
int val = compute(nums[left], nums[right]);
if (val == target) {
// 处理结果
left++;
right--;
} else if (val < target) {
left++; // 需要增大
} else {
right--; // 需要减小
}
}4.2 快慢指针模板
// 适用：原地操作，慢指针维护有效区间
int slow = 0;
for (int fast = 0; fast < nums.length; fast++) {
if (condition(nums[fast], nums[slow])) {
slow++;
nums[slow] = nums[fast]; // 或做其他操作
}
}
return slow + 1; // 有效长度4.3 固定窗口模板
int windowSize = k;
int windowSum = 0;
// 建立初始窗口
for (int i = 0; i < windowSize; i++) {
windowSum += nums[i];
}
int result = windowSum;
// 滑动窗口
for (int right = windowSize; right < nums.length; right++) {
windowSum += nums[right]; // 加入右侧新元素
windowSum -= nums[right - windowSize]; // 移出左侧旧元素
result = Math.max(result, windowSum);
}
return result;4.4 可变窗口模板
// 适用：子数组/子串的最长/最短问题
Map<Character, Integer> window = new HashMap<>();
int left = 0;
int result = 0; // 或 Integer.MAX_VALUE（求最小时）
for (int right = 0; right < s.length(); right++) {
char c = s.charAt(right);
window.merge(c, 1, Integer::sum); // 加入右侧元素
// 窗口不满足条件时，收缩左侧
while (!isValid(window)) {
char leftChar = s.charAt(left);
window.merge(leftChar, -1, Integer::sum);
if (window.get(leftChar) == 0) window.remove(leftChar);
left++;
}
// 更新最优解
result = Math.max(result, right - left + 1);
}
return result;4.5 题型对应指南
| 题目特征 | 推荐模式 | 关键信号词 |
|---|---|---|
| 有序数组找两数之和 | 对撞指针 | 非递减、目标和 |
| 原地删除/移动 | 快慢指针 | 原地、O(1) 空间 |
| 链表找中间/环 | 快慢指针 | 链表、环、中间节点 |
| 固定长度子数组最值 | 固定滑窗 | 长度为 k 的子数组 |
| 最长无重复子串 | 可变滑窗 + HashMap | 不重复、最长子串 |
| 最小覆盖子串 | 可变滑窗 + 字符计数 | 覆盖、最小子串 |
| 容积/接雨水 | 对撞指针 + 前缀最值 | 高度、容器、雨水 |
知识星球
完整 LeetCode 200题题解、大厂真题笔试原题，扫码加入「AI 工程师加速社区」👉 立即加入