前言
本专栏主要通过“LeetCode 热题100”，来捡起自己本科阶段的算法知识与技巧。语言主要使用c++/java。如果同样正在练习LeetCode 热题100的朋友欢迎关注或订阅本专栏。有疑问欢迎留言交流~
题目描述
题目链接
给定两个字符串 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 * 104
s 和 p 仅包含小写字母
思路
暴力解法： 判断一个字符串是否为异位词，最简单可以暴力排序，如果两个字符串排序后是一样的，则两个字符串为异位词。然后通过截取子字符串即可，最终提交超时，C++代码如下：
class Solution {
public:vector<int> findAnagrams(string s, string p) {int size_s = s.size();int size_p = p.size();vector<int> ans;// 如果s的长度小于p的长度，直接返回空if (size_s < size_p) return ans;// 对p进行排序string sorted_p = p;sort(sorted_p.begin(), sorted_p.end());// 遍历s，检查每个长度为p.size()的子串for (int i = 0; i <= size_s - size_p; i++) {string substr = s.substr(i, size_p); // 获取子串string sorted_substr = substr; // 将子串复制一份进行排序sort(sorted_substr.begin(), sorted_substr.end());// 如果排序后的子串与p排序后的子串相同，则为异位词if (sorted_substr == sorted_p) {ans.push_back(i); // 记录起始索引}}return ans;}
};
正规解法： 很经典的滑动窗口题目。控制跟字符串p一样的一个窗口在字符串s中滑动。然后判断是否存在异位词。判断的方法不能去用排序了，时间复杂度太高。可以去记录每个字符出现的次数（本题适用是因为字符串保证全为小写字母），然后调用字符串重写的equals方法去判断两个数组是否内容是相同的即可。写了一个Java版本，代码如下：
class Solution {public List<Integer> findAnagrams(String s, String p) {//滑动窗口int p_len = p.length();int s_len = s.length();if (s_len < p_len) {return new ArrayList<Integer>();}List<Integer> ans = new ArrayList<Integer>();int[] s_count = new int[26];int[] p_count = new int[26];for (int i=0; i<p_len; i++){p_count[p.charAt(i) - 'a']++;s_count[s.charAt(i) - 'a']++;}for (int i=0; i<=s_len - p_len;i++){System.out.println(i);if (Arrays.equals(s_count, p_count)){//用重写的equals方法直接判断ans.add(i);}--s_count[s.charAt(i) - 'a'];//这个地方做一下特判，防止最后一个字符还去算下一次的状况if (i + p_len < s_len){++s_count[s.charAt(i + p_len) - 'a'];}}return ans;}
}
