LeetCode（438 子串异位词）
https://leetcode.cn/problems/find-all-anagrams-in-a-string?envType=study-plan-v2&envId=top-100-liked
自己解法
这道题在最开始做的时候，我考虑到了使用一个长度为26的数组来进行辅助解决，但是忽视了维护它，考虑到每次为子串都建立一个数组会增加时空开销所以放弃。
那么回到这题的正确解法中：使用长度为26的数组，并每取得下一个子串的时候进行维护。
因为每次取下一个子串的时候都是丢弃头部的字符，添加最后一个字符，所以我们只需要进行维护即可。
代码如下：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
| class Solution {
public List<Integer> findAnagrams(String s, String p) {
int sLen = s.length();
int pLen = p.length();
if(sLen<pLen){
return new ArrayList();
}
List<Integer> subStringIndex = new ArrayList();
int[] sCount = new int[26];
int[] pCount = new int[26];
for(int i = 0;i<pLen ;i++){
++ sCount[s.charAt(i) - 'a'];
++ pCount[p.charAt(i) - 'a'];
}
for(int i = 0; i<= sLen - pLen; i++){
if(Arrays.equals(sCount,pCount)){
subStringIndex.add(i);
}
if(i+pLen<sLen){
sCount[s.charAt(i) - 'a']--;
sCount[s.charAt(i+pLen) - 'a']++;
}
}
return subStringIndex;
}
}
|
注意一个细节，因为当循环走到最后一个子串的时候，如果我们对维护数组的代码不进行条件判断，就会报数组越界异常。
解决方法很简单，就是在维护数组的代码进行判断，当且仅当能在s串中取到完整的长度为pLen的时候才进行维护。
这样就避免了数组越界问题。
其他解法
力扣的官方题解中，还优化了这个滑动窗口的作用。
我们不再维护“记录字母出现次数”的两个数组，改为维护一个“每种字母差几个”的一个数组。
再维护一个类flag值：differ，用于记录当前还有几个字母有差距。
这个数组的长度也是26，但是注意：
- 当某个位置上的值为 0 的时候，说明子串距离 p 串在这个字母上已经完整了。
- 当某个位置上的值为 负数 m 的时候，说明子串距离 p 串在这个字母上还缺 m 个该字母。
- 当某个位置上的值为 正数 n 的时候，说明子串距离 p 串在这个字母上多了 n 个该字母。
那么在正式循环中，我们就会考虑：
判断一下当前位置的 differ 是否为0 ：如果为 0 就为输出 List 中加上当前的子串索引。
如果目前子串的第一个字符对应的数组值：
- 正好为 1 的时候，说明正好多了一个，我们马上丢掉这个字符后，这个字母就齐了。
- 正好为 0 的时候，说明原本是齐了，丢掉后缺了一个。
这两个操作都会导致 differ 产生变动，所以在正式的数组维护操作前，先把标记位进行加一或减一。
主逻辑 1：进行一次数组的维护（去头）
如果目前子串的最后一个字符的下一位（即将加入子串的字符）对应的数组值：
- 正好为 -1 的时候，说明正好缺一个，我们马上加上这个字母后，这个字母就正好齐了。
- 正好为 0 的时候，说明原本齐了，现在加了一个多了。
同样，这样的操作也会导致 differ 产生变动，所以在正式的数组维护操作前，先把标记位进行加一或减一。
主逻辑2：进行一次数组的维护（加尾）
最后我们还需要考虑一件事：就是当最后一轮的时候，只需要进行判断 differ 的值，不需要进行数组的维护了（后面没有字母添加进子串了）。
所以在维护数组代码的外面要包一层判断语句。
最后代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
| class Solution {
public List<Integer> findAnagrams(String s, String p) {
int sLen = s.length(), pLen = p.length();
if (sLen < pLen) {
return new ArrayList<Integer>();
}
List<Integer> ans = new ArrayList<Integer>();
int[] count = new int[26];
for (int i = 0; i < pLen; ++i) {
++count[s.charAt(i) - 'a'];
--count[p.charAt(i) - 'a'];
}
int differ = 0;
for (int j = 0; j < 26; ++j) {
if (count[j] != 0) {
++differ;
}
}
for (int i = 0; i <= sLen - pLen; ++i) {
if (differ == 0) {
ans.add(i);
}
if(i+pLen < sLen){
if (count[s.charAt(i) - 'a'] == 1) {
--differ;
} else if (count[s.charAt(i) - 'a'] == 0) {
++differ;
}
--count[s.charAt(i) - 'a'];
if (count[s.charAt(i + pLen) - 'a'] == -1) {
--differ;
} else if (count[s.charAt(i + pLen) - 'a'] == 0) {
++differ;
}
++count[s.charAt(i + pLen) - 'a'];
}
}
return ans;
}
}
|