1. 无重复字符的最长子串
（s 由英文字母、数字、符号和空格组成）
1.1 题目解析
这道题要求找到一个字符串中不包含重复字符的最长子串的长度。子串必须是连续的字符序列，不是子序列，不能跳着选字符。
1.2 暴力解法
最开始的想法很简单：把每个可能的子串都检查一遍。从字符串的第一个字符开始，看看能往右延伸多远不出现重复字符，记录这个长度，然后从第二个字符开始同样检查，一直试完所有起始位置。
class Solution {
public:
int lengthOfLongestSubstring(string s) {
int n = s.size();
if(n == 0) return 0;
int maxlength = 1;
for(int i = 0; i < n; i++) {
int a[256] = {0}; // 用数组记录字符出现次数
for(int j = i; j < n; j++) {
int k = (int)s[j]; // 字符转成 ASCII 码值
a[k]++;
if(a[k] == 2) { // 某个字符出现两次，说明有重复
maxlength = max(maxlength, j - i);
break;
}
maxlength = max(maxlength, j - i + 1);
}
}
return maxlength;
}
};
这个方法很直观，但效率太低。外层循环遍历每个起始位置，内层循环从起始位置向右延伸检查重复。对于长度为 n 的字符串，最坏情况下要检查 n²/2 个子串，时间复杂度是 O(n²)。当字符串很长时，这个算法会超时。
1.3 优化思路：滑动窗口
注意到暴力解法中有很多重复计算：比如检查从 i 到 j 的子串没有重复后，检查从 i 到 j+1 的子串时，其实只需要判断 s[j+1] 这个字符是否在前面出现过，不需要重新检查整个子串。
如果用滑动窗口的方法，维护一个窗口，窗口里的字符都是不重复的。右指针不断向右扩展窗口，当遇到重复字符时，左指针向右移动直到窗口内没有重复字符。
int lengthOfLongestSubstring(string s) {
unordered_map<char, int> charIndex; // 记录每个字符最近出现的位置
int n = s.size();
int maxlength = 0;
int left = 0; // 窗口左边界
for(int right = 0; right < n; right++) { // 如果当前字符已存在且在窗口内
if(charIndex.count(s[right]) && charIndex[s[right]] >= left) {
left = charIndex[s[right]] + 1; // 左边界跳到重复字符的下一位
}
charIndex[s[right]] = right; // 更新字符位置
maxlength = max(maxlength, right - left + 1); // 更新最大长度
}
return maxlength;
}
这个算法的关键是用哈希表记录每个字符最近出现的位置。右指针一直向右移动，左指针只有遇到重复字符时才移动。这样每个字符最多被访问两次（右指针一次，左指针一次），时间复杂度降到 O(n)。
这里有个细节要注意：判断字符是否在窗口内时，不仅要看这个字符是否出现过，还要看它最近出现的位置是否在 left 的右边。因为字符可能在窗口外面出现过，这种重复不影响当前窗口。
2. 找到字符串中所有字母异位词
（s 和 p 只包含小写字母）
2.1 题目解析
这道题要在字符串 s 中找到所有是 p 的异位词的子串，返回这些子串的起始索引。异位词指的是字母相同但顺序可以不同的词，比如"abc"和"bca"是异位词。
2.2 初始思路
看到这道题，觉得很适合用滑动窗口，因为要找的是固定长度的子串。窗口长度就是 p 的长度，我们需要检查每个这个长度的窗口是否是 p 的异位词。
class Solution {
public:
vector<int> findAnagrams(string s, string p) {
vector<int> result;
if(s.length() < p.length()) return result; // s 比 p 短，不可能有异位词
// 记录 p 中每个字符的出现次数
vector<int> pCount(26, 0);
for(char c : p) {
pCount[c - 'a']++;
}
// 记录窗口内字符的出现次数
vector<int> windowCount(26, 0);
int windowSize = p.length(); // 初始化第一个窗口
for(int i = 0; i < windowSize; i++) {
windowCount[s[i] - 'a']++;
}
// 检查第一个窗口
if(windowCount == pCount) {
result.push_back(0);
}
// 滑动窗口
for(int i = windowSize; i < s.length(); i++) {
// 移除窗口左边字符
windowCount[s[i - windowSize] - 'a']--;
// 添加窗口右边新字符
windowCount[s[i] - 'a']++;
// 检查当前窗口是否是异位词
(windowCount == pCount) {
result.(i - windowSize + );
}
}
result;
}
};
这个方法维护一个固定长度的窗口，每次滑动时更新窗口内字符计数，然后比较窗口计数和 p 的计数是否相同。时间复杂度是 O(n)，空间复杂度是 O(1)（因为只有 26 个小写字母）。
2.3 进一步优化
上面的方法需要每次都比较两个 26 位的数组，虽然常数时间，但还可以优化。可以用一个变量记录窗口和 p 的差异程度。
vector<int> findAnagrams(string s, string p) {
vector<int> result;
int sLen = s.length(), pLen = p.length();
if(sLen < pLen) return result;
vector<int> count(26, 0); // 初始化：p 中的字符加 1，窗口中的字符减 1
// 这样如果 count 中某个字符为 0，表示这个字符在 p 和窗口中数量相同
for(int i = 0; i < pLen; i++) {
count[p[i] - 'a']++;
count[s[i] - 'a']--;
}
int diff = 0; // 记录有多少个字符的数量不匹配
for(int num : count) {
if(num != 0) diff++;
}
if(diff == 0) result.push_back(0); // 滑动窗口
for(int i = pLen; i < sLen; i++) {
char leftChar = s[i - pLen] - 'a';
char rightChar = s[i] - 'a';
// 移除左边字符
if(count[leftChar] == 0) diff++; // 原来匹配，现在移除后不匹配了
count[leftChar]++;
if(count[leftChar] == 0) diff--; // 现在又匹配了
// 添加右边字符
if(count[rightChar] == ) diff++;
count[rightChar]--;
(count[rightChar] == ) diff--;
(diff == ) result.(i - pLen + );
}
result;
}
这个优化的好处是不用每次比较两个数组，只需要维护一个 diff 变量，表示有多少个字符在窗口和 p 中数量不同。当 diff 为 0 时，窗口就是 p 的异位词。每次窗口滑动时，只需要更新移出字符和移入字符对 diff 的影响。
3. 算法特点总结
滑动窗口算法特别适合处理连续子串或子数组问题。它的核心思想是维护一个窗口，通过移动窗口的左右边界来遍历所有可能的子串/子数组，同时高效地更新窗口状态。
3.1 窗口的三种类型
- 固定长度窗口：像第二题，窗口长度固定为 p 的长度，每次滑动一个位置检查
- 可变长度窗口：像第一题，窗口长度根据条件变化，右指针扩展窗口，左指针在条件不满足时收缩窗口
- 多指针窗口：有些复杂问题可能需要多个指针协同工作
3.2 滑动窗口的优点
- 通常能将 O(n²) 的暴力解法优化到 O(n)
- 思路清晰，代码结构统一
- 适合处理连续区间问题
