高频算法题型：双指针与滑动窗口
2026/6/27大约 8 分钟
高频算法题型：双指针与滑动窗口
高频算法题型：双指针与滑动窗口是计算机科学的核心，它为问题解决提供了高效的计算方法。
本文介绍了高频算法题型：双指针与滑动窗口的设计思路和实现方式，帮助你提升编程能力。
双指针就是在遍历过程中用两个指针协同工作，根据指针移动方式的不同，分为三类：
- 对撞指针：一个从头，一个从尾，相向而行
- 快慢指针：两个都从头出发，速度不同
- 前后指针：一前一后同向移动（也叫追逐步指针）
1.2 对撞指针模板
public int[] twoPointer(int[] nums, int target) {
int left = 0, right = nums.length - 1;
while (left < right) {
int sum = nums[left] + nums[right];
if (sum == target) {
return new int[]{left, right};
} else if (sum < target) {
left++; // 和太小，左指针右移
} else {
right--; // 和太大，右指针左移
}
}
return new int[]{-1, -1};
}二、滑动窗口核心思想
2.1 什么是滑动窗口？
滑动窗口是对撞指针的变体——两个指针同向移动，维护一个"窗口"。窗口内的元素满足某个条件时，尝试扩大窗口；不满足时，缩小窗口。
2.2 通用模板
public int slidingWindowTemplate(String s, String t) {
// 1. 初始化窗口计数
Map<Character, Integer> need = new HashMap<>();
Map<Character, Integer> window = new HashMap<>();
for (char c : t.toCharArray()) {
need.put(c, need.getOrDefault(c, 0) + 1);
}
int left = 0, right = 0;
int valid = 0; // 满足条件的字符数
// 2. 扩大窗口
while (right < s.length()) {
char c = s.charAt(right);
right++;
if (need.containsKey(c)) {
window.put(c, window.getOrDefault(c, 0) + 1);
if (window.get(c).equals(need.get(c))) {
valid++;
}
}
// 3. 收缩窗口（当窗口满足条件时）
while (valid == need.size()) {
// 更新结果
// ...
char d = s.charAt(left);
left++;
if (need.containsKey(d)) {
if (window.get(d).equals(need.get(d))) {
valid--;
}
window.put(d, window.get(d) - 1);
}
}
}
return result;
}三、10 道经典题详解
第 1 题：两数之和 II（LeetCode 167）
题目： 有序数组中找两个数，使它们的和等于 target。
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) {
return new int[]{left + 1, right + 1}; // 题目要求 1-indexed
} else if (sum < target) {
left++;
} else {
right--;
}
}
return new int[]{-1, -1};
}复杂度： O(n) 时间，O(1) 空间
第 2 题：三数之和（LeetCode 15）
题目： 找出数组中所有和为 0 的三元组。
public List<List<Integer>> threeSum(int[] nums) {
List<List<Integer>> result = new ArrayList<>();
Arrays.sort(nums); // 先排序！
for (int i = 0; i < nums.length - 2; i++) {
// 去重
if (i > 0 && nums[i] == nums[i - 1]) continue;
// 剪枝优化
if (nums[i] > 0) break; // 最小的数都 > 0，不可能和为 0
int left = i + 1, right = nums.length - 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]));
// 去重
while (left < right && nums[left] == nums[left + 1]) left++;
while (left < right && nums[right] == nums[right - 1]) right--;
left++;
right--;
} else if (sum < 0) {
left++;
} else {
right--;
}
}
}
return result;
}关键点： 排序 + 去重 + 剪枝
第 3 题：盛最多水的容器（LeetCode 11）
题目： 两条竖线与 x 轴围成的容器能盛最多水。
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;
}核心思想： 移动较短的板，因为移动较长的板不可能得到更大的面积。
第 4 题：接雨水（LeetCode 42）
题目： 给定柱子高度，计算能接多少雨水。
双指针解法：
public int trap(int[] height) {
int left = 0, right = height.length - 1;
int leftMax = 0, rightMax = 0;
int water = 0;
while (left < right) {
leftMax = Math.max(leftMax, height[left]);
rightMax = Math.max(rightMax, height[right]);
if (leftMax < rightMax) {
// 左边较低，水量取决于左边最大高度
water += leftMax - height[left];
left++;
} else {
water += rightMax - height[right];
right--;
}
}
return water;
}理解关键： 每个位置能接的雨水量 = min(左边最大高度, 右边最大高度) - 当前高度。双指针同时从两边计算，哪边的 max 小就处理哪边。
第 5 题：最小覆盖子串（LeetCode 76）
题目： 在 s 中找到包含 t 所有字符的最短子串。
public String minWindow(String s, String t) {
Map<Character, Integer> need = new HashMap<>();
Map<Character, Integer> window = new HashMap<>();
for (char c : t.toCharArray()) {
need.put(c, need.getOrDefault(c, 0) + 1);
}
int left = 0, right = 0;
int valid = 0;
int start = 0, len = Integer.MAX_VALUE;
while (right < s.length()) {
char c = s.charAt(right);
right++;
if (need.containsKey(c)) {
window.put(c, window.getOrDefault(c, 0) + 1);
if (window.get(c).equals(need.get(c))) {
valid++;
}
}
while (valid == need.size()) {
if (right - left < len) {
start = left;
len = right - left;
}
char d = s.charAt(left);
left++;
if (need.containsKey(d)) {
if (window.get(d).equals(need.get(d))) {
valid--;
}
window.put(d, window.get(d) - 1);
}
}
}
return len == Integer.MAX_VALUE ? "" : s.substring(start, start + len);
}这就是滑动窗口模板的直接应用！ 先扩大窗口找可行解，再收缩窗口找最优解。
第 6 题：无重复字符的最长子串（LeetCode 3）
题目： 找出字符串中不含重复字符的最长子串长度。
public int lengthOfLongestSubstring(String s) {
Map<Character, Integer> window = new HashMap<>();
int left = 0, right = 0;
int maxLen = 0;
while (right < s.length()) {
char c = s.charAt(right);
right++;
window.put(c, window.getOrDefault(c, 0) + 1);
// 有重复字符时收缩
while (window.get(c) > 1) {
char d = s.charAt(left);
left++;
window.put(d, window.get(d) - 1);
}
maxLen = Math.max(maxLen, right - left);
}
return maxLen;
}第 7 题：找到字符串中所有字母异位词（LeetCode 438）
题目： 找到 s 中所有 t 的字母异位词的起始索引。
public List<Integer> findAnagrams(String s, String t) {
List<Integer> result = new ArrayList<>();
Map<Character, Integer> need = new HashMap<>();
Map<Character, Integer> window = new HashMap<>();
for (char c : t.toCharArray()) {
need.put(c, need.getOrDefault(c, 0) + 1);
}
int left = 0, right = 0, valid = 0;
while (right < s.length()) {
char c = s.charAt(right);
right++;
if (need.containsKey(c)) {
window.put(c, window.getOrDefault(c, 0) + 1);
if (window.get(c).equals(need.get(c))) {
valid++;
}
}
// 窗口大小等于 t 的长度时收缩
while (right - left >= t.length()) {
if (valid == need.size()) {
result.add(left);
}
char d = s.charAt(left);
left++;
if (need.containsKey(d)) {
if (window.get(d).equals(need.get(d))) {
valid--;
}
window.put(d, window.get(d) - 1);
}
}
}
return result;
}第 8 题：移动零（LeetCode 283）
题目： 将数组中所有 0 移到末尾，保持非零元素相对顺序。
public void moveZeroes(int[] nums) {
// 快慢指针：slow 指向下一个非零位置
int slow = 0;
for (int fast = 0; fast < nums.length; fast++) {
if (nums[fast] != 0) {
// 交换
int temp = nums[slow];
nums[slow] = nums[fast];
nums[fast] = temp;
slow++;
}
}
}第 9 题：环形链表（LeetCode 141 & 142）
题目： 判断链表是否有环，若有环找到入环节点。
// 判断是否有环
public boolean hasCycle(ListNode head) {
ListNode slow = head, fast = head;
while (fast != null && fast.next != null) {
slow = slow.next; // 慢指针走1步
fast = fast.next.next; // 快指针走2步
if (slow == fast) return true;
}
return false;
}
// 找入环节点
public ListNode detectCycle(ListNode head) {
ListNode slow = head, fast = head;
while (fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
if (slow == fast) {
// 相遇后，一个从 head 出发，一个从相遇点出发
ListNode ptr = head;
while (ptr != slow) {
ptr = ptr.next;
slow = slow.next;
}
return ptr; // 入环节点
}
}
return null;
}数学证明： 设 head 到入环点距离为 a，入环点到相遇点距离为 b，相遇点到入环点距离为 c。则 2(a+b) = a + b + n(b+c)，化简得 a = (n-1)(b+c) + c，即从 head 走 a 步等于从相遇点走 c 步（绕 n-1 圈）。
第 10 题：长度最小的子数组（LeetCode 209）
题目： 找出和 ≥ target 的最短连续子数组。
public int minSubArrayLen(int target, int[] nums) {
int left = 0, right = 0;
int sum = 0;
int minLen = Integer.MAX_VALUE;
while (right < nums.length) {
sum += nums[right];
right++;
while (sum >= target) {
minLen = Math.min(minLen, right - left);
sum -= nums[left];
left++;
}
}
return minLen == Integer.MAX_VALUE ? 0 : minLen;
}四、双指针 vs 滑动窗口总结
4.1 什么时候用双指针？
- 数组/链表有有序性 → 对撞指针
- 需要检测环 → 快慢指针
- 需要原地操作（去重、移动元素）→ 前后指针
4.2 什么时候用滑动窗口？
- 求子串/子数组的最值
- 窗口满足某种约束条件
- 窗口内元素有统计关系（计数/求和）
4.3 滑动窗口判断流程
1. 窗口内是什么？（满足条件的子串/子数组）
2. right 扩大窗口时如何更新？
3. 什么时候收缩窗口？（窗口满足条件时）
4. left 收缩窗口时如何更新？
5. 结果在哪里更新？（收缩窗口内更新最优解）五、面试要点与总结
高频面试题
Q1：滑动窗口的时间复杂度怎么分析？
答：虽然是双重 while 循环，但 left 和 right 各自最多遍历一次数组，所以时间复杂度是 O(n)。窗口内的操作通常是 O(1)（HashMap 增删）。
Q2：三数之和为什么要排序？
答：(1) 排序后才能用双指针（对撞指针需要有序性）；(2) 排序后方便去重（相同元素相邻）。
Q3：接雨水有哪些解法？
答：三种：(1) 双指针 O(n) O(1)；(2) 动态规划预计算左右最大值 O(n) O(n)；(3) 单调栈 O(n) O(n)。双指针最优。
Q4：盛水容器为什么移动较短的一边？
答：面积 = min(h[left], h[right]) × (right - left)。移动较长的一边，宽度减小，高度不会增加（仍然受限于较短边），面积一定减小。只有移动较短边才有可能找到更大的面积。
Q5：滑动窗口模板的 valid 变量是什么意思？
答：valid 记录当前窗口中有多少种字符满足要求（数量达到 need 中的要求）。当 valid == need.size() 时，窗口包含了所有需要的字符，可以开始收缩。
总结
双指针和滑动窗口的核心就两句话：
- 双指针： 利用有序性或快慢关系，将 O(n²) 暴力搜索优化到 O(n)
- 滑动窗口： 维护一个动态窗口，先扩大找可行解，再收缩找最优解
记住滑动窗口模板的四个步骤：右扩 → 更新 → 判断 → 左缩。遇到子串/子数组题目，先想想能不能套这个模板。
一句话总结： 双指针考的是思路灵巧，滑动窗口考的是模板熟练。刷题时先判断类型，再套模板，最后处理边界。