滑动窗口技术
滑动窗口（Sliding Window）常用于处理数组或字符串的连续子问题。通过维护一个窗口的两端，避免了重复的嵌套遍历，将时间复杂度从 O(n²) 优化到 O(n)。
滑动窗口的核心思想是：维护一个可变大小的窗口，窗口内的元素满足某种条件。当窗口需要扩展时，右指针右移；当窗口需要收缩时，左指针右移。
适用场景：
- 子串/子数组问题
- 需要连续元素满足条件的问题
- 求最长/最短满足条件的子串
3. 无重复字符的最长子串 (Longest Substring Without Repeating Characters)
题目描述
给定一个字符串 s，请你找出其中不含有重复字符的最长子串的长度。
示例 1：
输入：s = "abcabcbb"
输出：3
解释：因为无重复字符的最长子串是 "abc"，所以其长度为 3。
示例 2：
输入：s = "bbbbb"
输出：1
解释：因为无重复字符的最长子串是 "b"，所以其长度为 1。
示例 3：
输入：s = "pwwkew"
输出：3
解释：因为无重复字符的最长子串是 "wke"，所以其长度为 3。
请注意，你的答案必须是 子串 的长度，"pwke" 是一个子序列，不是子串。
约束条件：
0 <= s.length <= 5 * 10^4s由英文字母、数字、符号和空格组成
解题思路
这道题要求找不含重复字符的最长子串，是一个典型的滑动窗口问题。
方法一：暴力枚举
枚举所有子串，检查是否含有重复字符。时间复杂度 O(n³)，会超时。
方法二：滑动窗口 + 哈希集合
使用一个哈希集合维护当前窗口内的字符。右指针扩展窗口，如果遇到重复字符，左指针收缩直到窗口内无重复。
方法三：滑动窗口 + 哈希表（优化）
使用哈希表记录每个字符最后出现的位置。遇到重复字符时，可以直接将左指针跳到重复字符上次出现位置的下一个位置，避免逐个移动。
图解示例
以 s = "abcabcbb" 为例：
方法二（哈希集合）演示：
初始：left=0, right=0, window={}, maxLen=0
第1步：right=0, char='a'
window={a}, 不重复
maxLen = max(0, 1) = 1
第2步：right=1, char='b'
window={a,b}, 不重复
maxLen = max(1, 2) = 2
第3步：right=2, char='c'
window={a,b,c}, 不重复
maxLen = max(2, 3) = 3
第4步：right=3, char='a' ← 'a' 已在窗口中！
收缩窗口：移除 s[left]=s[0]='a', left=1
window={b,c,a}, 不重复
maxLen = max(3, 3) = 3
第5步：right=4, char='b' ← 'b' 已在窗口中！
收缩窗口：移除 s[left]=s[1]='b', left=2
window={c,a,b}, 不重复
maxLen = max(3, 3) = 3
第6步：right=5, char='c' ← 'c' 已在窗口中！
收缩窗口：移除 s[left]=s[2]='c', left=3
window={a,b,c}, 不重复
maxLen = max(3, 3) = 3
第7步：right=6, char='b' ← 'b' 已在窗口中！
收缩窗口：移除 s[left]=s[3]='a', left=4, 'b' 还在窗口
收缩窗口：移除 s[left]=s[4]='b', left=5
window={c,b}, 不重复
maxLen = max(3, 2) = 3
第8步：right=7, char='b' ← 'b' 已在窗口中！
收缩窗口：移除 s[left]=s[5]='c', left=6, 'b' 还在窗口
收缩窗口：移除 s[left]=s[6]='b', left=7
window={b}, 不重复
maxLen = max(3, 1) = 3
最终结果：3
Java 代码实现
方法二：滑动窗口 + 哈希集合
class Solution {
public int lengthOfLongestSubstring(String s) {
// 哈希集合存储当前窗口内的字符
Set<Character> window = new HashSet<>();
int left = 0, right = 0; // 左右指针
int maxLen = 0; // 最长无重复子串长度
while (right < s.length()) {
char ch = s.charAt(right);
// 如果字符不在窗口中，扩展窗口
if (!window.contains(ch)) {
window.add(ch);
right++;
maxLen = Math.max(maxLen, right - left);
} else {
// 如果字符在窗口中，收缩窗口
// 移除最左边的字符，直到窗口中无重复
window.remove(s.charAt(left));
left++;
}
}
return maxLen;
}
}
方法三：滑动窗口 + 哈希表（优化）
class Solution {
public int lengthOfLongestSubstring(String s) {
// 哈希表记录每个字符最后出现的索引
Map<Character, Integer> charIndex = new HashMap<>();
int left = 0, right = 0;
int maxLen = 0;
while (right < s.length()) {
char ch = s.charAt(right);
// 如果字符已在窗口中（索引 >= left）
if (charIndex.containsKey(ch) && charIndex.get(ch) >= left) {
// 直接跳到重复字符的下一个位置
left = charIndex.get(ch) + 1;
}
// 更新字符的最新索引
charIndex.put(ch, right);
right++;
// 更新最大长度
maxLen = Math.max(maxLen, right - left);
}
return maxLen;
}
}
复杂度分析
方法二：
- 时间复杂度：O(2n) = O(n)，每个字符最多被访问两次（右指针一次，左指针一次）
- 空间复杂度：O(min(m, n))，m 是字符集大小
方法三：
- 时间复杂度：O(n)，每个字符只被访问一次
- 空间复杂度：O(min(m, n))，m 是字符集大小
易错点
-
方法三中判断重复：必须检查
charIndex.get(ch) >= left，因为哈希表可能存有窗口外的旧索引。 -
窗口大小计算：窗口大小是
right - left，因为 right 已经自增，指向下一个待处理字符。 -
空字符串处理：代码已自然处理空字符串情况（返回 0）。
438. 找到字符串中所有字母异位词 (Find All Anagrams in a String)
题目描述
给定两个字符串 s 和 p，找到 s 中所有 p 的异位词的子串，返回这些子串的起始索引。不考虑答案输出顺序。
异位词指由相同字母重排列形成的字符串（包括相同的字符串）。
示例 1：
输入：s = "cbaebabacd", p = "abc"
输出：[0,6]
解释：
起始索引等于 0 的子串是 "cba"，它是 "abc" 的异位词。
起始索引等于 6 的子串是 "bac"，它是 "abc" 的异位词。
示例 2：
输入：s = "abab", p = "ab"
输出：[0,1,2]
解释：
起始索引等于 0 的子串是 "ab"，它是 "ab" 的异位词。
起始索引等于 1 的子串是 "ba"，它是 "ab" 的异位词。
起始索引等于 2 的子串是 "ab"，它是 "ab" 的异位词。
约束条件：
1 <= s.length, p.length <= 3 * 10^4s和p仅包含小写英文字母
解题思路
这道题要求在字符串 s 中找到所有与 p 互为异位词的子串。异位词的特点是两个字符串的字符组成完全相同，只是顺序可能不同。
方法：固定窗口滑动 + 字符计数
- 用一个长度为 26 的数组统计
p中每个字符的出现次数 - 维护一个固定大小为
p.length()的滑动窗口 - 统计窗口内字符的出现次数，如果与
p的字符计数相同，则找到一个异位词
图解示例
以 s = "cbaebabacd", p = "abc" 为例：
pCount = {a:1, b:1, c:1}
窗口大小 = 3
初始窗口 s[0:3] = "cba":
sCount = {a:1, b:1, c:1}
与 pCount 相同 → 找到异位词，记录索引 0
滑动窗口 s[1:4] = "bae":
移除 'c'，添加 'e'
sCount = {a:1, b:1, e:1}
与 pCount 不同
滑动窗口 s[2:5] = "aeb":
移除 'b'，添加 'b'
sCount = {a:1, b:1, e:1}
与 pCount 不同
滑动窗口 s[3:6] = "eba":
移除 'a'，添加 'a'
sCount = {a:1, b:1, e:1}
与 pCount 不同
滑动窗口 s[4:7] = "bab":
移除 'e'，添加 'b'
sCount = {a:1, b:2}
与 pCount 不同
滑动窗口 s[5:8] = "aba":
移除 'b'，添加 'a'
sCount = {a:2, b:1}
与 pCount 不同
滑动窗口 s[6:9] = "bac":
移除 'a'，添加 'c'
sCount = {a:1, b:1, c:1}
与 pCount 相同 → 找到异位词，记录索引 6
滑动窗口 s[7:10] = "acd":
移除 'b'，添加 'd'
sCount = {a:1, c:1, d:1}
与 pCount 不同
最终结果：[0, 6]
Java 代码实现
class Solution {
public List<Integer> findAnagrams(String s, String p) {
List<Integer> result = new ArrayList<>();
int sLen = s.length(), pLen = p.length();
// 边界条件：如果 s 比 p 短，不可能有异位词
if (sLen < pLen) {
return result;
}
// 统计 p 中每个字符的出现次数
int[] pCount = new int[26];
// 统计当前窗口中每个字符的出现次数
int[] sCount = new int[26];
// 初始化：统计 p 的字符计数和 s 的第一个窗口
for (int i = 0; i < pLen; i++) {
pCount[p.charAt(i) - 'a']++;
sCount[s.charAt(i) - 'a']++;
}
// 检查第一个窗口
if (Arrays.equals(pCount, sCount)) {
result.add(0);
}
// 滑动窗口遍历剩余部分
for (int i = 0; i < sLen - pLen; i++) {
// 移除窗口左边的字符
sCount[s.charAt(i) - 'a']--;
// 添加窗口右边的新字符
sCount[s.charAt(i + pLen) - 'a']++;
// 检查当前窗口是否是异位词
if (Arrays.equals(pCount, sCount)) {
result.add(i + 1);
}
}
return result;
}
}
复杂度分析
时间复杂度：O(n × k)，其中 n 是 s 的长度，k 是字符集大小（这里是 26）。每次比较数组需要 O(26)。
可以优化到 O(n)，通过维护一个计数器，记录有多少个字符的计数是匹配的。
空间复杂度：O(k)，k 是字符集大小，这里是 O(26) = O(1)。
优化实现
使用一个计数变量记录匹配的字符数量：
class Solution {
public List<Integer> findAnagrams(String s, String p) {
List<Integer> result = new ArrayList<>();
int sLen = s.length(), pLen = p.length();
if (sLen < pLen) return result;
int[] count = new int[26];
// 初始化：p 中的字符计数为正，s 窗口中的字符计数为负
for (int i = 0; i < pLen; i++) {
count[p.charAt(i) - 'a']++;
count[s.charAt(i) - 'a']--;
}
// 统计有多少个字符计数为 0（即匹配）
int match = 0;
for (int c : count) {
if (c == 0) match++;
}
if (match == 26) result.add(0);
// 滑动窗口
for (int i = 0; i < sLen - pLen; i++) {
// 移除左边的字符
int left = s.charAt(i) - 'a';
if (count[left] == 0) match--;
count[left]++;
if (count[left] == 0) match++;
// 添加右边的字符
int right = s.charAt(i + pLen) - 'a';
if (count[right] == 0) match--;
count[right]--;
if (count[right] == 0) match++;
// 所有字符都匹配
if (match == 26) result.add(i + 1);
}
return result;
}
}
相关题目
- 567. 字符串的排列 - 类似思路
- 76. 最小覆盖子串 - 变长滑动窗口
- 209. 长度最小的子数组 - 变长滑动窗口