目录
🌼无重复字符 -- 最长子串
AC 滑动窗口（桶）
🌼所有字母异位词
AC 滑动窗口 + 桶
AC 滑动窗口（优化）
🌼无重复字符 -- 最长子串
一开始考虑用 BF暴力 或者 KMP 的，后来想想，KMP 得到的是
主串中子串出现的位置，不适合本题，转而采用双指针 -- 滑动窗口 的思路
AC 滑动窗口（桶）
O(n) 复杂度，具体思路，样例模拟下
判断重复字符 -- 桶（新建一个bool 数组）
class Solution {
public:
int lengthOfLongestSubstring(string s) {
int ans = 0, ret = 0, vis[130] = {0};
// i 左指针 j 右指针
for (int i = 0, j = 0; j < s.size();) {
if (vis[int(s[j])] == 0) { // 子串不存在该字符
ans++, ret = max(ret, ans);
vis[int(s[j])] = 1; // 出现 1 次
j++;
}
else { // 子串中存在该字符
while (vis[int(s[j])] > 0) {
vis[int(s[i])]--;
i++;
ans--;
}
// 直到重复字符去掉了
// 当前字符加入子串
ans++, ret = max(ret, ans);
vis[int(s[j])]++;
j++;
}
}
return ret;
}
};🌼所有字母异位词
AC 滑动窗口 + 桶
坑1
i 左指针，j 右指针
for 遍历整个字符串 s 时，每次循环末尾，不要忘了减去当前 i 的出现次数，再加上 j + 1 出现次数
坑2
注意 i, j 范围，i 是滑动窗口 左端点，j 滑动窗口 右端点
所以 j < n - 1
O( m + (n - m)*26 ) n -- 字符串 s 长度 m -- 字符串 p 长度
class Solution {
public:
vector<int> findAnagrams(string s, string p) {
int n = s.size(), m = p.size();
// 特判 s 长度 < p 的情况
if (n < m || !n)
return {}; // 返回空数组
int vis[30] = {0}; // p 中出现次数
int b[30] = {0}; // 当前 子串 出现次数
vector<int> ans; // 返回的答案
for (int i = 0; i < m; ++i)
vis[p[i] - 'a']++; // 统计 p 中字母出现次数
for (int i = 0; i < m; ++i)
b[s[i] - 'a']++; // 统计子串字母出现次数
// i 左指针 j 右指针
for (int i = 0, j = m - 1; j < n; i++, j++) {
int flag = 1;
for (int t = 0; t < 26; ++t) // 判断是否异位词
if (vis[t] != b[t]) {
flag = 0; // 不是
break;
}
if (flag)
ans.push_back(i);
if (j < n - 1) // 防止越界
b[s[i] - 'a']--, b[s[j + 1] - 'a']++; // 更新 子串 字母出现次数
}
return ans;
}
};AC 滑动窗口（优化）
思路
只需要一个辅助数组 count[], 即 c[]，统计每个字母的差值
比如 c[s[i] - 'a']++, c[p[i] - 'a']--;
再借助一个 differ 变量 -- 统计 字符串 p 和 滑动窗口，数量不同字母的个数
坑1
n - m 次 for 循环中，分类讨论时，要小心，differ 分 4 种情况 + / -，而不是 2 种
坑2
越界问题，for 循环中，有 s[j + 1]，那么 for ( ; j < n - 1; )
坑3
c[x]-- 和 c[y]++ 要分开
因为 x, y 有可能代表同一个字母
O(m + 26 + n)
class Solution {
public:
vector<int> findAnagrams(string s, string p) {
int n = s.size(), m = p.size();
vector<int> ans;
if (n < m || !n) return {}; // 特判
int c[30] = {0}; // 每个字母 差值
int differ = 0; // 数量不同字母的 个数
for (int i = 0; i < m; ++i) { // 前 m 个
c[s[i] - 'a']++; // s 中字母出现次数
c[p[i] - 'a']--; // p 中字母出现次数
}
for (int i = 0; i < 26; ++i)
if (c[i] != 0) differ++;
if (differ == 0)
ans.push_back(0); // 初始位置
// i 左指针, j 右指针, 滑动窗口
for (int i = 0, j = m - 1; j < n - 1; ++i, ++j) {
// x 窗口左端点前一个, y 窗口右端点
// [i, j] 原来窗口 [i+1, j+1] 新窗口
int x = s[i] - 'a', y = s[j + 1] - 'a';
// 错误的↓ -- 卡了半个小时
// c[x]--, c[y]++; // 窗口右移，此消彼长
c[x]--;
if (c[x] == 0) differ--; // 1 -> 0, 不同 -> 同
else if (c[x] == -1) differ++; // 0 -> -1, 同 -> 不同
c[y]++;
if (c[y] == 0) differ--; // -1 -> 0 不同 -> 同
else if (c[y] == 1) differ++; // 0 -> 1 同 -> 不同
if (differ == 0)
ans.push_back(i + 1);
}
return ans;
}
};
