这道题主要是利用"窗口"这一概念，优化的时候可以利用题目本身的特殊性。
原题
给定一个字符串 s 和一个非空字符串 p，找到 s 中所有是 p 的字母异位词的子串，返回这些子串的起始索引。
字符串只包含小写英文字母，并且字符串 s 和 p 的长度都不超过 20100。
说明：
- 字母异位词指字母相同，但排列不同的字符串。
- 不考虑答案输出的顺序。
示例 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" 的字母异位词。
原题url：https://leetcode-cn.com/problems/find-all-anagrams-in-a-string/
解题
利用"窗口"思想
这道题类似字符串完全匹配，只是这道题要求连续但顺序可以不一致。这样就无法利用待匹配字符串预先构造了。
那么结合这道题，为了能够让我们知道当前字符是否在待匹配字符串中，我们需要一个集合存储。
为了能够让我们知道各个字符出现了几次，我们需要一个哈希表，并且实时更新其次数，如果次数为0，则移除该项，如果哈希表为空，则说明找到了，记录开始下标，并且窗口滑动。
结合上面的思路，我们可以写出代码：
class Solution {
public List<Integer> findAnagrams(String s, String p) {
// 最终结果
List<Integer> result = new LinkedList<>();
if (s == null || s.length() == 0) {
return result;
}
// 根据p构造map，key代表字符，value代表相应次数
Map<Character, Integer> map = new HashMap<>();
for (Character character : p.toCharArray()) {
map.put(character, map.getOrDefault(character, 0) + 1);
}
// p中所有的字符
Set<Character> pCharSet = new HashSet<>(map.keySet());
// 每个字母出现的位置，value表示每一次出现的下标
Map<Character, LinkedList<Integer>> indexMap = new HashMap<>();
// 开始的下标
int first = 0;
char[] sArray = s.toCharArray();
// 遍历s
for (int i = 0; i < sArray.length; i++) {
Character character = sArray[i];
// 如果character不在pCharSet中，说明该字符不存在
if (!pCharSet.contains(character)) {
// 则重新构造indexMap
indexMap = new HashMap<>();
// 从first位置到i位置，还原map
for (int j = first; j < i; j++) {
character = sArray[j];
map.put(character, map.getOrDefault(character, 0) + 1);
}
// 重置first的位置
first = i + 1;
continue;
}
// 从indexMap中获取该字符出现的位置
LinkedList<Integer> indexList = indexMap.computeIfAbsent(character, k -> new LinkedList<>());
// 在末尾记录当前位置
indexList.add(i);
// map中相应字符剩余出现次数
Integer count = map.get(character);
// 如果次数为null，说明无法再减
if (count == null) {
// 从开始下标到该字符第一次出现的下标，还原map和indexMap
int firstIndex = indexList.removeFirst();
for (int j = first; j < firstIndex; j++) {
character = sArray[j];
map.put(character, map.getOrDefault(character, 0) + 1);
indexMap.get(character).removeFirst();
}
// 重置first的位置
first = firstIndex + 1;
continue;
}
// 次数-1
count--;
// 如果次数不为0，则重新放进map中
if (count > 0) {
map.put(character, count);
continue;
}
// 如果次数减为0，则移除该项
map.remove(character);
// 检查map是否为空
if (!map.isEmpty()) {
continue;
}
// 如果为空，说明满足条件，记录进result中
result.add(first);
// first向后移动1个（窗口滑动）
character = sArray[first];
map.put(character, map.getOrDefault(character, 0) + 1);
indexMap.get(character).removeFirst();
first++;
}
return result;
}
}
提交OK，但执行用时很慢，需要优化。
优化
上面解法查询慢，我感觉根本原因在于使用了比较复杂的数据结构，包括集合、哈希表、链表等，虽然 Java 中针对这些结构做了优化，但相比于最基础的结构数组而言，在查找和更新上还是更慢了。这道题可以用数组的主要原因在于只会出现26个小写英文字母。这样用了数组之后，查找和更新都快了太多。大家可以根据这个思路优化试试。
既然有提到窗口，那么我们就将这个思想用到极致。可以先将窗口设置的大一些，比如至少包含目标字符串里的所有字符。达成条件后，就开始把左边开始缩小，直到缩小成目标字符串的长度后，然后记录进结果中，之后窗口右移，重复上述过程。
接下来看看代码：
class Solution {
public List<Integer> findAnagrams(String s, String p) {
if(s == null || s.length() == 0) return new ArrayList<>();
List<Integer> res = new ArrayList<>();
// 需要的字符，由于都是小写字母，因此直接用26个长度的数组代替原来的HashMap
int[] needs = new int[26];
for(char ch : p.toCharArray()) {
needs[ch - 'a'] ++;
}
// "窗口"
int[] window = new int[26];
// 窗口的左右下标
int left = 0, right = 0;
// 用total检测窗口中是否已经涵盖了p中的所有字符
int total = p.length();
// 遍历s
while(right < s.length()) {
char chr = s.charAt(right);
// 如果该字符在p中出现过
if(needs[chr - 'a'] > 0) {
// 则在窗口中记下该字符
window[chr - 'a'] ++;
// 如果当前窗口中该字符的数量，小于需要的数量
if(window[chr - 'a'] <= needs[chr - 'a']) {
// 则total数量减1
total --;
}
}
// total为0，说明窗口中包含了p中所有字符
while(total == 0) {
// (right - left + 1)代表窗口的大小
// 如果窗口的大小等于p，说明符合要求
if(right - left + 1 == p.length()){
// 记录左指针
res.add(left);
}
// 左指针向右移动1个
char chl = s.charAt(left);
left ++;
// 如果左指针属于p中
if(needs[chl - 'a'] > 0) {
// 那么窗口中该字符的数量也需要减1
window[chl - 'a'] --;
// 如果窗口中该字符的数量小于需要的数量
if(window[chl - 'a'] < needs[chl - 'a']) {
// 则total加1，跳出循环，说明还需要继续向右寻找
total ++;
}
}
}
// 继续向右寻找
right ++;
}
return res;
}
}
提交OK，执行时间加快了一个量级。
总结
以上就是这道题目我的解答过程了，不知道大家是否理解了。这道题主要是利用"窗口"这一概念，优化的时候可以利用题目本身的特殊性。
有兴趣的话可以访问我的博客或者关注我的公众号、头条号，说不定会有意外的惊喜。
公众号：健程之道
网友评论