分类
定长滑动窗口
定长滑动窗口
例题
1456. 定长子串中元音的最大数目
1343. 大小为 K 且平均值大于等于阈值的子数组数目
643. 子数组最大平均数 I
题解和思路
定长滑窗的思路可以分成三步：
- 进窗口 2. 更新答案 3.出窗口。
例题：
1456. 定长子串中元音的最大数目
入：下标为 i 的元素进入窗口，更新相关统计量。如果 i<k−1 则重复第一步。
更新：更新答案。一般是更新最大值/最小值。
出：下标为 i−k+1 的元素离开窗口，更新相关统计量。
需要特别注意的是，这个思路是在循环中保证了长度为K的窗口，进和出在一起发生，因此更新答案在进和出的中间。
思路很简单，当不满足长度时持续进入窗口，满足长度的 时刻 来记录和更新答案，然后（对于下一轮循环会多出的项）移除
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
| class Solution {
public int maxVowels(String s, int k) {
int left = 0, right = 0;
Set<Character> vowelSet = new HashSet<>();
vowelSet.add('a');
vowelSet.add('e');
vowelSet.add('i');
vowelSet.add('o');
vowelSet.add('u');
int count = 0;
int ret = 0;
char[] stochar = s.toCharArray();
for (int i = 0; i < s.length(); i++) {
char inChar = stochar[i];
if (vowelSet.contains(inChar)) {
count++;
}
if (i < k - 1) {
continue;
}
ret = Math.max(count, ret);
char outChar = stochar[i - k + 1];
if (vowelSet.contains(outChar)) {
count--;
}
}
return ret;
}
}
|
（也可以使用left, right）或者先处理窗口再移动
1343. 大小为 K 且平均值大于等于阈值的子数组数目
同样的思路
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
| class Solution {
public int numOfSubarrays(int[] arr, int k, int threshold) {
int count = 0;
int n = arr.length;
int sum = 0;
for (int i = 0; i < n; i++) {
sum += arr[i];
if (i < k - 1) {
continue;
}
if (sum / k >= threshold) {
count++;
}
sum -= arr[i - k + 1];
}
return count;
}
}
|
643. 子数组最大平均数 I
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
| class Solution {
public double findMaxAverage(int[] nums, int k) {
int n = nums.length;
double avg = -10e4;
int sum = 0;
for (int i = 0; i < n; i++) {
int num = nums[i];
sum += num;
if (i < k - 1) {
continue;
}
avg = Math.max(avg, (double) sum / k);
sum -= nums[i - k + 1];
}
return avg;
}
}
|
不定长总结：
首先滑动窗口在于一个「单调性」，移动某一个指针（一般为右指针）能够使值单调增加/减少，移动另一个指针（一般为左指针）能够使得值单调减少/增加
越长越合法
一般要写 ans += left
滑动窗口的内层循环结束时，右端点固定在 right，左端点在 0, 1, 2, ... , left−1 的所有子数组（子串）都是合法的，这一共有 left 个
「关键」在于如何reuse结果，是一个视角的问题通过 1358. 包含所有三种字符的子字符串数目 来进行分析
例题
1358. 包含所有三种字符的子字符串数目
2962. 统计最大元素出现至少 K 次的子数组
题解
1358. 包含所有三种字符的子字符串数目
比如此题存在两种视角：
numberOfSubstringsMethod1 方法中是以left为开头，所有从right开始的到n的子串都合法：
[left, right] [left, right + 1] [left, right + 2] … [left, n - 1] 所以有 n - right 个
所以在每一次inner while loop中，left每移动一次就需要更新答案。
而
numberOfSubstringsMethod2 方法则是以right为结尾，所有 左端点为0到left - 1 的字符串都满足条件:
[0, right] [1, right] [2, right] … [left - 1, right] 所以有 left 个
所以在每一次inner while loop「结束后」再更新答案
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
| class Solution {
public int numberOfSubstrings(String s) {
return numberOfSubstringsMethod2(s);
}
private int numberOfSubstringsMethod1(String s) {
char[] sChar = s.toCharArray();
int n = s.length();
int count = 0;
int left = 0, right = 0;
int[] hs = new int[3];
while (right < n) {
hs[sChar[right] - 'a']++;
while (hs[0] >= 1 && hs[1] >= 1 && hs[2] >= 1) {
count += n - right;
char leftChar = sChar[left];
hs[leftChar - 'a']--;
left++;
}
right++;
}
return count;
}
private int numberOfSubstringsMethod2(String s) {
char[] sChar = s.toCharArray();
int n = s.length();
int count = 0;
int left = 0, right = 0;
int[] hs = new int[3];
while (right < n) {
hs[sChar[right] - 'a']++;
while (hs[0] >= 1 && hs[1] >= 1 && hs[2] >= 1) {
char leftChar = sChar[left];
hs[leftChar - 'a']--;
left++;
}
count += left;
right++;
}
return count;
}
}
|
2962. 统计最大元素出现至少 K 次的子数组
同理：可以直接秒杀这道题
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
| class Solution {
public long countSubarrays(int[] nums, int k) {
int left = 0, right = 0;
int n = nums.length;
int max = Arrays.stream(nums).max().getAsInt();
int count = 0;
long ret = 0;
while (right < n) {
if (nums[right] == max) {
count++;
}
while (count >= k) {
ret += n - right;
if (nums[left] == max) count--;
left++;
}
right++;
}
return ret;
}
}
|
越短越合法
关键在于如何理解 「增量」
首先我们看看窗口内的子数组怎么“数”的问题，比如数组[1,2,3,4]，当前窗口[1,2,3]。
我们全量数一次窗口内的子数组: [1], [1,2], [1,2,3], [2], [2,3], [3], 一共6个，当right右移后，窗口变成[1,2,3,4]，这时如果我们再进行“全量数”，上一个窗口[1,2,3]就被重复计算了。
为了消除这种重复，我们需要使用“增量数”，从右向左看，right右移后，窗口新增一个元素，会新增哪些子数组？ 例如[1,2,3] -> [1,2,3,4] 窗口内新增一个元素4时，新增的子数组肯定要包含4，以4为右端点，新增的子数组是[4],[3,4],[2,3,4],[1,2,3,4]， 一共4个，这个增量就是窗口大小right-left+1。
那么为什么是 right - left + 1
当窗口右端 right 向右移动一位时，窗口内新增了一个元素。为了计算由于这个新增元素所带来的新增子数组数量，我们需要考虑以新元素为右端点的所有子数组。
具体来说，所有以位置 right 为右端点、左端点从 left 到 right 之间的子数组，都是新增的。这些子数组形式如下：
- 从位置
left 到 right 的子数组 [A[left], A[left+1], ..., A[right]]
- 从位置
left+1 到 right 的子数组 [A[left+1], ..., A[right]]
- …
- 从位置
right 到 right 的子数组 [A[right]]
总共有 right - left + 1 个子数组。这是因为左端点可以取从 left 到 right 的任意位置，共计 right - left + 1 个可能。
因此，right - left + 1 表示了新增的子数组数量，即以新元素为右端点的所有可能子数组的数量。这些子数组在之前的窗口中并不存在，所以不会造成重复计数。
例题
713. 乘积小于 K 的子数组
题解
713. 乘积小于 K 的子数组
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
| class Solution {
public int numSubarrayProductLessThanK(int[] nums, int k) {
int n = nums.length;
int left = 0, right = 0;
int count = 0;
int mult = 1;
if (k <= 1) return 0;
while (right < n) {
mult *= nums[right];
while (mult >= k) {
mult /= nums[left];
left++;
}
count += right - left + 1;
right++;
}
return count;
}
}
|
