滑动窗口与双指针：高频算法题的通用解题框架
2026/4/30大约 9 分钟
滑动窗口与双指针：高频算法题的通用解题框架
适读人群：备战面试、系统学习算法的Java开发 | 阅读时长：约17分钟 | 文章类型：算法框架+题型总结
开篇故事
去年帮一个朋友老胡备战面试，他反复刷力扣，刷了一个月，做了200多道题，但发现一个问题：同类型的题，换个包装他又不会做了。比如"最长无重复子串"他会，但"最小覆盖子串"就卡住了。
我说：你是在背题，不是在学方法。
他说：那我怎么学方法？
我说：滑动窗口和双指针是一套框架，你把这套框架的代码模板记住，然后分析每道题该往哪里套。不是背题目，是背模板+套路。
他说：你有模板吗？
我说：有，但不是你想的那种直接背的模板。是一套思考流程，你按这个流程分析题目，自然就知道该写什么。
然后我花了一下午给他整理了这篇内容。一周后他去面试，滑动窗口和双指针那几道题全过了。
今天我把这套思考框架公开出来。
一、什么时候用滑动窗口
核心判断：题目要求在连续子数组/子串中找某个最优解（最长/最短/恰好某个值），并且这个子数组/子串有可以用两个指针界定的特征。
典型题型：
- 最长无重复子串
- 最小覆盖子串
- 长度最小的子数组（和>=target）
- 找所有字母异位词
滑动窗口的通用框架：
窗口 = [left, right)（左闭右开）
right向右扩展：把新元素加入窗口，更新窗口状态
当窗口满足（或不满足）条件时，left向右收缩：从窗口移除元素，更新窗口状态二、完整代码实现
2.1 滑动窗口通用模板
package com.laozhang.sliding;
import java.util.*;
/**
* 滑动窗口通用模板与经典题目实现
* 覆盖：最长/最短子数组，字符频次匹配等场景
*/
public class SlidingWindowSolutions {
/**
* 题型1：最长无重复子串（LeetCode 3）
*
* 框架套用：
* - 窗口：[left, right)，维护一个字符计数map
* - 扩展条件：right < s.length()
* - 收缩条件：窗口内出现重复字符（某字符计数>1）
* - 求最长：每次right扩展后（窗口合法时）更新答案
*/
public static int lengthOfLongestSubstring(String s) {
Map<Character, Integer> window = new HashMap<>(); // 窗口内字符计数
int left = 0, right = 0;
int maxLen = 0;
while (right < s.length()) {
// 1. right扩展：新字符入窗口
char c = s.charAt(right++);
window.merge(c, 1, Integer::sum);
// 2. 窗口不合法（有重复）时，收缩left直到合法
while (window.get(c) > 1) {
char leftChar = s.charAt(left++);
window.merge(leftChar, -1, Integer::sum);
if (window.get(leftChar) == 0) window.remove(leftChar);
}
// 3. 窗口合法，更新最大长度
maxLen = Math.max(maxLen, right - left);
}
return maxLen;
}
/**
* 题型2：最小覆盖子串（LeetCode 76）
*
* 框架套用：
* - 窗口维护：字符计数 + valid计数（已满足t中多少不同字符的需求）
* - 扩展：right一直扩展
* - 收缩条件：窗口满足覆盖t的条件时，尝试收缩找更短的
* - 求最短
*/
public static String minWindow(String s, String t) {
// need：t中各字符需要的数量
// window：当前窗口中各字符的数量
Map<Character, Integer> need = new HashMap<>();
Map<Character, Integer> window = new HashMap<>();
for (char c : t.toCharArray()) need.merge(c, 1, Integer::sum);
int left = 0, right = 0;
int valid = 0; // window中满足need条件的字符种类数
int minLen = Integer.MAX_VALUE, minLeft = 0;
while (right < s.length()) {
// 1. 扩展right
char c = s.charAt(right++);
if (need.containsKey(c)) {
window.merge(c, 1, Integer::sum);
// 如果这个字符的数量恰好满足need，valid+1
if (window.get(c).equals(need.get(c))) valid++;
}
// 2. 当窗口满足条件（覆盖了t的所有字符），尝试收缩
while (valid == need.size()) {
// 更新最小覆盖子串
if (right - left < minLen) {
minLen = right - left;
minLeft = left;
}
// 收缩left
char d = s.charAt(left++);
if (need.containsKey(d)) {
if (window.get(d).equals(need.get(d))) valid--; // 不再满足需求
window.merge(d, -1, Integer::sum);
}
}
}
return minLen == Integer.MAX_VALUE ? "" : s.substring(minLeft, minLeft + minLen);
}
/**
* 题型3：长度最小的子数组（LeetCode 209）
* 找和>=target的最短连续子数组
*
* 框架套用：求最短，窗口满足条件时立刻收缩
*/
public static int minSubArrayLen(int target, int[] nums) {
int left = 0, right = 0;
int sum = 0, minLen = Integer.MAX_VALUE;
while (right < nums.length) {
sum += nums[right++]; // 扩展
while (sum >= target) { // 满足条件时持续收缩
minLen = Math.min(minLen, right - left);
sum -= nums[left++]; // 收缩
}
}
return minLen == Integer.MAX_VALUE ? 0 : minLen;
}
/**
* 题型4：找所有字母异位词（LeetCode 438）
* 固定窗口大小（p.length()），找所有与p字母相同（忽略顺序）的子串起始下标
*
* 这是固定窗口大小的滑动窗口，更简单
*/
public static List<Integer> findAnagrams(String s, String p) {
List<Integer> result = new ArrayList<>();
if (s.length() < p.length()) return result;
// 对比两个字符频次数组（只有26个小写字母）
int[] need = new int[26];
int[] window = new int[26];
for (char c : p.toCharArray()) need[c - 'a']++;
for (int right = 0; right < s.length(); right++) {
window[s.charAt(right) - 'a']++; // 右边字符入窗口
if (right >= p.length()) {
// 窗口超出固定大小：移除左边字符
window[s.charAt(right - p.length()) - 'a']--;
}
if (right >= p.length() - 1 && Arrays.equals(window, need)) {
result.add(right - p.length() + 1);
}
}
return result;
}
}2.2 双指针：对撞指针与快慢指针
package com.laozhang.twopointer;
import java.util.*;
/**
* 双指针的两种形态：对撞指针和快慢指针
*
* 对撞指针：left从左，right从右，相向而行，适合有序数组
* 快慢指针：slow和fast同向，fast比slow快，适合链表/原地修改
*/
public class TwoPointerSolutions {
/**
* 对撞指针1：两数之和（有序数组版，LeetCode 167）
*/
public static 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};
else if (sum < target) left++; // 和太小，增大左指针
else right--; // 和太大，减小右指针
}
return new int[]{-1, -1};
}
/**
* 对撞指针2：三数之和（LeetCode 15）
* 固定一个数i，对[i+1, n-1]区间用对撞指针找两数之和
*/
public static 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 (nums[i] > 0) break; // 第一个数已经大于0，不可能凑成0
if (i > 0 && nums[i] == nums[i-1]) continue; // 去重
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;
}
/**
* 快慢指针1：移除元素（原地，LeetCode 27）
* slow指针：下一个有效元素应该放的位置
* fast指针：当前遍历的元素
*/
public static int removeElement(int[] nums, int val) {
int slow = 0;
for (int fast = 0; fast < nums.length; fast++) {
if (nums[fast] != val) {
nums[slow++] = nums[fast]; // 有效元素放到slow位置
}
}
return slow; // slow就是新数组的长度
}
/**
* 快慢指针2：判断链表是否有环（Floyd判圈算法）
*/
static class ListNode {
int val; ListNode next;
ListNode(int val) { this.val = val; }
}
public static boolean hasCycle(ListNode head) {
ListNode slow = head, fast = head;
while (fast != null && fast.next != null) {
slow = slow.next; // 慢指针走一步
fast = fast.next.next; // 快指针走两步
if (slow == fast) return true; // 相遇即有环
}
return false;
}
/**
* 快慢指针3：找链表中点
* fast走完时，slow恰好在中点
*/
public static ListNode findMiddle(ListNode head) {
ListNode slow = head, fast = head;
while (fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
}
return slow; // slow即为中点
}
public static void main(String[] args) {
System.out.println("最长无重复子串 'abcabcbb': " +
SlidingWindowSolutions.lengthOfLongestSubstring("abcabcbb")); // 3
System.out.println("最小覆盖子串 s='ADOBECODEBANC', t='ABC': " +
SlidingWindowSolutions.minWindow("ADOBECODEBANC", "ABC")); // "BANC"
System.out.println("长度最小子数组 target=7: " +
SlidingWindowSolutions.minSubArrayLen(7, new int[]{2,3,1,2,4,3})); // 2
System.out.println("字母异位词下标 s='cbaebabacd', p='abc': " +
SlidingWindowSolutions.findAnagrams("cbaebabacd", "abc")); // [0, 6]
System.out.println("三数之和 [-1,0,1,2,-1,-4]: " +
TwoPointerSolutions.threeSum(new int[]{-1,0,1,2,-1,-4}));
// [[-1,-1,2],[-1,0,1]]
}
}四、踩坑实录
坑1：滑动窗口里valid计数没有正确维护
报错现象：最小覆盖子串问题，valid计数出错，导致找到了不符合条件的子串。
根本原因：valid的增减时机搞错了。valid应该在"窗口中某字符的数量恰好等于need中该字符的需求"时加1，而不是每次该字符入窗口都加1。
具体解法：
// 错误：每次入窗口都加valid
window.merge(c, 1, Integer::sum);
if (need.containsKey(c)) valid++; // 错！同一字符可能被计多次
// 正确：只有恰好满足need时才加valid
window.merge(c, 1, Integer::sum);
if (need.containsKey(c) && window.get(c).equals(need.get(c))) valid++; // 用equals！
// 注意：Integer的==比较对-128到127以外的值不可靠，必须用equals()！坑2：Integer的==比较陷阱
报错现象：window.get(c) == need.get(c)有时返回false，即使两个值相等。
根本原因：Map.get()返回Integer对象，两个Integer对象用==比较的是引用，不是值。Integer的缓存范围是-128到127，超出这个范围的Integer对象用==会返回false。
具体解法：
// 错误：Integer的==比较
if (window.get(c) == need.get(c)) // 可能错！
// 正确：用.equals()
if (window.get(c).equals(need.get(c))) // 永远正确
// 或者：手动拆箱
if (window.get(c).intValue() == need.get(c).intValue())坑3：双指针的有序前提没有验证
报错现象：对撞指针找两数之和，对无序数组用，结果不对。
根本原因：对撞指针的正确性依赖数组有序。无序数组用对撞指针会漏解。
具体解法：
// 对撞指针前必须排序（如果输入无序）
Arrays.sort(nums);
int left = 0, right = nums.length - 1;
// ... 对撞指针逻辑
// 如果排序会破坏索引信息（题目要求返回原始下标），
// 先保存(值, 原始下标)对，排序后操作，答案用原始下标五、总结与延伸
滑动窗口的通用框架：right扩展加新元素，条件满足时left收缩，窗口大小动态变化。 关键是想清楚"窗口合法/不合法的判断条件"，以及"right和left在什么条件下移动"。把这两个问题想清楚，框架代码几乎是固定的。
双指针有两种形态：对撞（有序数组）和快慢（链表/原地修改）。 选哪种取决于数据结构和目标。数组有序 + 找满足某条件的两个数 → 对撞；链表检测环/找中点/删除倒数第N个 → 快慢；数组原地去重/移除元素 → 快慢。
滑动窗口和双指针都是O(n)的线性算法，把暴力O(n²)或O(n²logn)优化到O(n)。 识别这个优化机会的关键是：题目里有"连续子数组"或"两个数/三个数之和"这样的关键词，配合"有序"或"窗口状态可以局部更新（不需要全量重算）"的特征。