[LeetCode 438/567] 找到字符串中所有字母异位词/字符串的排列（滑动窗口）

【LeetCode 438】找到字符串中所有字母异位词

题面：

思路：

哈希表+滑动窗口：也可用于 567
哈希表记录滑动窗口内字符个数，easy不详细赘述，俺代码可以继续优化，这里用了两个哈希表去做对比，可以优化成一个哈希表上的加减，当 $hash[c]==0$ 时，说明当前字符 $c$ 在字符串 $p$ 和滑动窗口内出现的次数相同。

代码：

vector<int> findAnagrams(string s, string p) {int n= (int)p.size();vector<int> hashP(26);vector<int> hash(26);vector<int> res;for(const auto& c : p) ++ hashP[c - 'a'];for(int i = 0, j = 0; j < (int)s.size(); ++j) {while(j - i + 1 > n) --hash[s[i++] - 'a'];hash[s[j] - 'a'] ++;if(j - i + 1 == n) {bool flag = true;for(size_t k = 0; k < 26; ++ k)if(hash[k] != hashP[k]) {flag = false;break;}if(flag) res.push_back(i);}}return res;
}

---

【LeetCode 567】字符串的排列

题面：

思路：

统计相同字符+滑动窗口：也可用于 438，微调一下就行

umm看了一下和官方题解差不多，就直接copy它的思路和代码了。

用 $cnt1$ 数组统计字符串 $s1$ 中各个字符的个数，$cnt2$ 数组统计当前字串（滑动窗口内）各个字符的个数。
用变量 $diff$ 统计 $cnt1$ 和 $cnt2$ 内不同值的个数。若 $diff==0$ 则说明 $cnt1==cnt2$，合法；否则说明 $cnt1\ne cnt2$，当前字串不是 $s1$ 的排列。

每次滑动窗口一进一出两个字符 $x$ 和 $y$。
若 $x=y$，则 $cnt2$ 无变化；
若 $x\ne y$，对于字符 $x$，若加入 $x$ 之前有 $cnt1[x]=cnt2[x]$，则说明加入 $x$ 之后失衡，$diff+1$；若加入 $x$ 之后有 $cnt1[x]=cnt2[x]$，说明加入 $x$ 之后 $x$ 在字串和 $s1$ 中出现的次数相同，$diff-1$。
注意： 可用 $cnt[x]=cnt2[x]-cnt1[x]$ 以简化上述流程，将 $cnt1[x]$ 与 $cnt2[x]$ 的比较替换成 $cnt[x]$ 与 $0$ 的比较。

代码：

bool checkInclusion(string s1, string s2) {int n = (int)s1.size(), m = (int)s2.size();if(n > m) return false;vector<int> cnt(26);int diff = 0;for(int i = 0; i < n; ++i) {-- cnt[s1[i] - 'a'];++ cnt[s2[i] - 'a'];}for(int c : cnt)if(c) ++ diff;if(!diff) return true;for(int i = n; i < m; ++i) {int x = s2[i] - 'a', y = s2[i - n] - 'a';if(x == y) continue;if(!cnt[x]) ++ diff;if(++ cnt[x] == 0) --diff;if(!cnt[y]) ++ diff;if(-- cnt[y] == 0) --diff;if(!diff) return true;}return false;
}

俺原本的代码：

bool checkInclusion(string s1, string s2) {if(s1.size() > s2.size()) return false;int n = (int)s1.size();unordered_map<int, int> mp;for(const auto& c : s1) ++ mp[c - 'a'];for(int i = 0, j = 0; j < (int)s2.size(); ++j) {while(j - i + 1 > n) {if(mp.find(s2[i] - 'a') != mp.end())mp[s2[i] - 'a'] ++;++i;}// 滑动窗口（字串）只统计在 s1 出现过的字符// 若当前字符 s2[j] 没在 s1 出现过，则继续遍历（因为加入 s2[j] 对结果无贡献）if(mp.find(s2[j] - 'a') != mp.end()) mp[s2[j] - 'a'] --;else continue;if(j - i + 1 == n) {bool flag = true;for(const auto& it : mp)if(it.second != 0) {flag = false;break;}if(flag) return true;}}return false;
}