438. Find All Anagrams in a String
Analysis
找出字符串 s 中存在的 p 的字母异位词。
Code
这种题很容易想到 $O(n^2)$ 的暴力解法,但是数据规模是 $[1, 3 × 10^4]$,毫无疑问会超时。按照题目的类型来看,应该是滑动窗口的题目,先把暴力解法写出来吧。1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19class Solution {
public:
vector<int> findAnagrams(string s, string p) {
int slen = s.length(), plen = p.length();
vector<int> cnt(26);
for(int i = 0; i < plen; i++) {
cnt[p[i] - 'a']++;
}
vector<int> ret;
for(int i = 0; i <= slen - plen; i++) {
vector<int> tmp(26);
for(int j = i; j < i + plen; j++) {
tmp[s[j] - 'a']++;
}
if(tmp == cnt) ret.push_back(i);
}
return ret;
}
};
没想到,这个暴力解法也能过。判断是否是字母异位词也可以用排序来实现,这是从昨天的题中学来的,但是排序的时间复杂度是 $O(nlogn)$,不如 $O(n)$ 的散列来的快。
现在再回头考虑如何用滑动窗口来处理:1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19class Solution {
public:
vector<int> findAnagrams(string s, string p) {
int slen = s.length(), plen = p.length();
if(slen < plen) return {};
vector<int> ret, cnt(26), tmp(26);
for(int i = 0; i < plen; i++) {
cnt[p[i] - 'a']++;
tmp[s[i] - 'a']++;
}
if(cnt == tmp) ret.push_back(0);
for(int i = 0; i < slen - plen; i++) {
tmp[s[i]- 'a']--;
tmp[s[i + plen] - 'a']++;
if(tmp == cnt) ret.push_back(i + 1);
}
return ret;
}
};
滑动窗口的难点在于如何理解窗口,就这个题来讲,窗口的大小就是字符串 p 的长度。每次滑动窗口的时候,就把左端的字符从窗口移出去,再把右端的字符加入到窗口中来。
官方题解还提供了一种优化版的滑动窗口思路,即不再统计窗口内字符的数量,只用一个变量 diff 来记录当前窗口字符串与 p 中数量不同的字母的个数。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
30class Solution {
public:
vector<int> findAnagrams(string s, string p) {
int slen = s.length(), plen = p.length();
if(slen < plen) return {};
vector<int> ret, cnt(26);
for(int i = 0; i < plen; i++) {
cnt[s[i] - 'a']++;
cnt[p[i] - 'a']--;
}
int diff = 0;
for(int i = 0; i < 26; i++) {
if(cnt[i] != 0) diff++;
}
if(diff == 0) ret.push_back(0);
for(int i = 0; i < slen - plen; i++) {
// left
if(cnt[s[i] - 'a'] == 1) diff--;
else if(cnt[s[i] - 'a'] == 0) diff++;
cnt[s[i] - 'a']--;
// right
if(cnt[s[i + plen] - 'a'] == -1) diff--;
else if(cnt[s[i + plen] - 'a'] == 0) diff++;
cnt[s[i + plen] - 'a']++;
// judge
if(diff == 0) ret.push_back(i + 1);
}
return ret;
}
};
注意下标为 0 时的判断得写在外面,目的是为了在滑动窗口的循环中先滑动窗口,再进行判断,这样就可以取到下标为 slen - plen 的位置了,且不至于越界。
翻了下评论区,好像还有一种滑动窗口的解法:1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22class Solution {
public:
vector<int> findAnagrams(string s, string p) {
int slen = s.length(), plen = p.length();
if(slen < plen) return {};
vector<int> ret, cnt(26);
for(int i = 0; i < plen; i++) {
cnt[p[i] - 'a']++;
}
int left = 0, right = 0;
while(right < slen) {
cnt[s[right] - 'a']--;
while(cnt[s[right] - 'a'] < 0) {
cnt[s[left] - 'a']++;
left++;
}
if(right - left + 1 == plen) ret.push_back(left);
right++;
}
return ret;
}
};
感觉这种解法不太好想,最好想的解法还是一开始的滑动窗口解法。滑动窗口的解法,应该是从双指针衍生出来的解法。难点在于,如何移动窗口的左端点 left,并同时将符合条件的解找出来。回到上面的解法来,巧妙之处在于在移动 left 的同时,让统计(也可以叫 hash)数组 cnt 还原了。
713. Subarray Product Less Than K
Analysis
找出乘积小于 k 且元素连续的子数组,这个题一看也是滑动窗口的题,也是 5 月 5 日的每日一题。
Code
暴力解法死在 93 个用例了😂。1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16class Solution {
public:
int numSubarrayProductLessThanK(vector<int>& nums, int k) {
if(k == 0) return 0;
int size = nums.size(), cnt = 0;
for(int i = 0; i < size; i++) {
int product = 1;
for(int j = i; j < size; j++) {
product *= nums[j];
if(product < k) cnt++;
else break;
}
}
return cnt;
}
};
直接换滑动窗口:1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18class Solution {
public:
int numSubarrayProductLessThanK(vector<int>& nums, int k) {
if(k == 0) return 0;
int size = nums.size(), cnt = 0;
int left = 0, right = 0, product = 1;
while(right < size) {
product *= nums[right];
while(left <= right && product >= k) {
product /= nums[left];
left++;
}
cnt += right - left + 1;
right++;
}
return cnt;
}
};
这里的难点在于理解子数组个数 cnt 的计算,这个值是随着滑动窗口的改变而改变的,每一次循环,加入或者减少元素,这个值都需要加上当前窗口内元素能构成的子数组个数。也就是说,当前窗口 $[left, right]$ 能构成的符合条件的子数组个数就是 $right - left + 1$ 个,把所有窗口的情况全加起来就是要求的结果了(这也是处理这类连续问题的关键)。
官方题解还提供了一种有趣的可以用二分来解决的方法:1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18class Solution {
public:
int numSubarrayProductLessThanK(vector<int>& nums, int k) {
if(k == 0) return 0;
int size = nums.size();
vector<double> logprefix(size + 1);
for(int i = 0; i < size; i++) {
logprefix[i + 1] = logprefix[i] + log(nums[i]);
}
double logk = log(k);
int cnt = 0;
for(int r = 0; r < size; r++) {
int l = upper_bound(logprefix.begin(), logprefix.begin() + r + 1, logprefix[r + 1] - logk + 1e-10) - logprefix.begin();
cnt += r + 1 - l;
}
return cnt;
}
};
这种方法需要用到前缀和、二分查找和数学知识,很灵活,不是那么好想。
Summary
滑动窗口掌握的还不熟练,还得再来点题目才行。