加载中…
应用场景：子串/子数组问题 · 最长无重复
交互式动画演示，可调整参数并单步执行。
全屏打开在数组/字符串题中，双指针 / 滑动窗口可以在线性时间 O(n) 内解决许多看似 O(n²) 的子数组问题，是面试最高频的题型之一。
它们的核心思想是：两个指针协同推进，避免内层循环的回退，使总步数为 O(n)。
sequenceDiagram participant left participant right Note over left,right: 初始化 left = 0, right = 0 right->>right: right++ 扩窗 right->>left: 窗口不合法？left++ 收缩 left->>right: 继续推进
有序数组找两数之和：
int left = 0, right = n - 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--;
}判链表是否有环：
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;原地去重：
int slow = 0;
for (int fast = 0; fast < n; fast++) {
if (nums[fast] != val) {
nums[slow++] = nums[fast];
}
}最长模板：
int left = 0, ans = 0;
int[] cnt = new int[128];
for (int right = 0; right < s.length(); right++) {
char c = s.charAt(right);
cnt[c]++;
while (/* 窗口不再合法 */) {
cnt[s.charAt(left)]--;
left++;
}
ans = Math.max(ans, right - left + 1);
}
return ans;最短模板：
int left = 0, ans = Integer.MAX_VALUE;
for (int right = 0; right < n; right++) {
while (/* 窗口合法 */) {
ans = Math.min(ans, right - left + 1);
left++;
}
}
return ans == Integer.MAX_VALUE ? 0 : ans;固定长度模板：
for (int right = 0; right < n; right++) {
if (right >= k - 1) {
left++;
}
}求字符串 s 中包含 t 所有字符的最短子串。
Map<Character, Integer> need = new HashMap<>();
for (char c : t.toCharArray()) need.merge(c, 1, Integer::sum);
int left = 0, valid = 0, start = 0, len = Integer.MAX_VALUE;
Map<Character, Integer> window = new HashMap<>();
for (int right = 0; right < s.length(); right++) {
char c = s.charAt(right);
window.merge(c, 1, Integer::sum);
if (need.containsKey(c) && window.get(c).equals(need.get(c))) valid++;
while (valid == need.size()) {
if (right - left + 1 < len) {
start = left; len = right - left + 1;
}
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 len == Integer.MAX_VALUE ? "" : s.substring(start, start + len);关键变量：
need: 目标频次window: 当前窗口频次valid: 满足要求的字符种类数（用于 O(1) 判断）求和 ≥ s 的最短连续子数组。
int left = 0, sum = 0, ans = Integer.MAX_VALUE;
for (int right = 0; right < n; right++) {
sum += nums[right];
while (sum >= s) {
ans = Math.min(ans, right - left + 1);
sum -= nums[left++];
}
}
return ans == Integer.MAX_VALUE ? 0 : ans;int lengthOfLongestSubstring(String s) {
Map<Character, Integer> last = new HashMap<>();
int left = 0, ans = 0;
for (int right = 0; right < s.length(); right++) {
char c = s.charAt(right);
if (last.containsKey(c)) {
left = Math.max(left, last.get(c) + 1);
}
last.put(c, right);
ans = Math.max(ans, right - left + 1);
}
return ans;
}关键技巧：left = Math.max(left, last.get(c) + 1) 而非 left = last.get(c) + 1——避免回退。
| 类型 | 适用 |
|---|---|
| 计数窗口 | "恰好出现 k 次""最多 k 个不同字符" |
| 频次窗口 | "包含所有字符""字符频次和恰好为 k" |
用 Map<Character, Integer> 计数 + valid 变量维护满足条件的字符种类数。
子数组和为 k 的问题：
int pre = 0, ans = 0;
Map<Integer, Integer> cnt = new HashMap<>();
cnt.put(0, 1);
for (int x : nums) {
pre += x;
ans += cnt.getOrDefault(pre - k, 0);
cnt.merge(pre, 1, Integer::sum);
}回文判断、字符串反转、单词反转：
char[] arr = s.toCharArray();
int l = 0, r = arr.length - 1;
while (l < r) {
char t = arr[l]; arr[l++] = arr[r]; arr[r--] = t;
}为什么滑动窗口是 O(n)？
核心：每个元素最多被
right进入一次，被left离开一次。两次访问总计 2n 次 → O(n)。
cnt[] 不更新，结果会错。ans 初始值 = MAX_VALUE 时要兜底返回 0。| 难度 | 题目 | 模型 |
|---|---|---|
| 🟢 | 长度最小的子数组 | 滑动窗口（最短） |
| 🟢 | 无重复字符的最长子串 | 滑动窗口（最长） |
| 🟡 | 最小覆盖子串 | 计数窗口 |
| 🟡 | 字符串的排列 | 计数窗口 |
| 🟡 | 替换后的最长重复字符 | 计数窗口 |
| 🟠 | 滑动窗口最大值 | 单调队列 |
| 🟠 | 找到字符串中所有字母异位词 | 计数窗口 |
| 🔴 | 最小窗口子序列 | 进阶计数窗口 |
右端前进扩窗口，窗口不合法则收缩，收缩至合法再扩。
最长问题：合法时记录答案；最短问题：合法时收缩。
public int minSubArrayLen(int s, int[] nums) {
int left = 0, sum = 0, ans = Integer.MAX_VALUE;
for (int right = 0; right < nums.length; right++) {
sum += nums[right];
while (sum >= s) {
ans = Math.min(ans, right - left + 1);
sum -= nums[left++];
}
}
return ans == Integer.MAX_VALUE ? 0 : ans;
}