题目描述
这是 LeetCode 上的 438. 找到字符串中所有字母异位词 ，难度为 中等。
Tag : 「双指针」、「滑动窗口」
给定两个字符串 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^41<=s.length,p.length<=3∗104
s和p仅包含小写字母
双指针（滑动窗口）
这是一道使用双指针实现滑动窗口的裸题。
具体的，我们可以先创建一个大小为 2626 的数组 c2c2 来统计字符串 p 的词频，另外一个同等大小的数组 c1c1 用来统计「滑动窗口」内的 s 的子串词频。
当两个数组所统计词频相等，说明找到了一个异位组，将窗口的左端点加入答案。
代码：
class Solution { public List<Integer> findAnagrams(String s, String p) { List<Integer> ans = new ArrayList<>(); int n = s.length(), m = p.length(); int[] c1 = new int[26], c2 = new int[26]; for (int i = 0; i < m; i++) c2[p.charAt(i) - 'a']++; for (int l = 0, r = 0; r < n; r++) { c1[s.charAt(r) - 'a']++; if (r - l + 1 > m) c1[s.charAt(l++) - 'a']--; if (check(c1, c2)) ans.add(l); } return ans; } boolean check(int[] c1, int[] c2) { for (int i = 0; i < 26; i++) { if (c1[i] != c2[i]) return false; } return true; } } 复制代码
- 时间复杂度：令
s和p的长度分别为 nn 和 mm，C = 26C=26 为字符集大小。统计p词频（构建 c2c2 数组）的复杂度为 O(m)O(m)；使用双指针检查s串的复杂度为 O(C * n)O(C∗n)。整体复杂度为 O(C*n + m)O(C∗n+m) - 空间复杂度：O(C)O(C)
优化 check
解法一中每次对滑动窗口的检查都不可避免需要检查两个词频数组，复杂度为 O(C)O(C)。
事实上，我们只关心两个数组是否完全一致，因而我们能够只维护一个词频数组 cntcnt 来实现。
起始处理 p 串时，只对 cntcnt 进行词频字符自增操作。当处理 s 的滑动窗口子串时，尝试对 cntcnt 中的词频进行「抵消/恢复」操作：
- 当滑动窗口的右端点右移时（增加字符），对 cntcnt 执行右端点字符的「抵消」操作；
- 当滑动窗口的左端点右移时（减少字符），对 cntcnt 执行左端点字符的「恢复」操作。
同时，使用变量 aa 统计 p 中不同字符的数量，使用变量 bb 统计滑动窗口（子串）内有多少个字符词频与 pp 相等。
当滑动窗口移动（ 执行「抵消/恢复」）时，如果「抵消」后该字符词频为 00，说明本次右端点右移，多产生了一位词频相同的字符；如果「恢复」后该字符词频数量为 11，说明少了一个为词频相同的字符。当且仅当 a = ba=b 时，我们找到了一个新的异位组。
代码：
class Solution { public List<Integer> findAnagrams(String s, String p) { List<Integer> ans = new ArrayList<>(); int n = s.length(), m = p.length(); int[] cnt = new int[26]; for (int i = 0; i < m; i++) cnt[p.charAt(i) - 'a']++; int a = 0; for (int i = 0; i < 26; i++) if (cnt[i] != 0) a++; for (int l = 0, r = 0, b = 0; r < n; r++) { // 往窗口增加字符，进行词频的抵消操作，如果抵消后词频为 0，说明有一个新的字符词频与 p 完全相等 if (--cnt[s.charAt(r) - 'a'] == 0) b++; // 若窗口长度超过规定，将窗口左端点右移，执行词频恢复操作，如果恢复后词频为 1（恢复前为 0），说明少了一个词频与 p 完全性相等的字符 if (r - l + 1 > m && ++cnt[s.charAt(l++) - 'a'] == 1) b--; if (b == a) ans.add(l); } return ans; } } 复制代码
- 时间复杂度：令
s和p的长度分别为 nn 和 mm，C = 26C=26 为字符集大小。构造 cntcnt 的复杂度为 O(m)O(m)，统计 pp 中不同的字符数量为 O(C)O(C)，对s进行滑动窗口扫描得出答案的复杂度为 O(n)O(n)。整体复杂度为 O(m + C + n)O(m+C+n) - 空间复杂度：O(C)O(C)
最后
这是我们「刷穿 LeetCode」系列文章的第 No.438 篇，系列开始于 2021/01/01，截止于起始日 LeetCode 上共有 1916 道题目，部分是有锁题，我们将先把所有不带锁的题目刷完。
在这个系列文章里面，除了讲解解题思路以外，还会尽可能给出最为简洁的代码。如果涉及通解还会相应的代码模板。
为了方便各位同学能够电脑上进行调试和提交代码，我建立了相关的仓库：github.com/SharingSour…
在仓库地址里，你可以看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其他优选题解。
