滑动窗口
一般我们在学习滑动窗口时,可以把它分为定长与不定长来针对性练习,滑动窗口实际上也可以看作是双指针,尤其是不定长的滑动窗口,本篇文章主要整理了一些比较有代表性的定长类滑动窗口的题型,以供练习。
1. 子数组最大平均数 I(简单)
1. 题目描述
1.2 解题思路
1.3 代码实现
public double findMaxAverage(int[] nums, int k) {
int sum = 0;
for (int i = 0; i < k; i++) {
sum += nums[i];
}
int maxSum = sum;
for (int i = k; i < nums.length; i++) {
sum = sum - nums[i - k] + nums[i];
maxSum = Math.max(maxSum, sum);
}
return (double) maxSum / k;
}
2. 找到一个数字的 K 美丽值(简单)
2.1 题目描述
2.2 解题思路
与第一题解题思路是一样的
2.3 代码实现
public int divisorSubstrings(int num, int k) {
StringBuilder sb = new StringBuilder();
String s = String.valueOf(num);
for (int i = 0; i < k; i++) {
sb.append(s.charAt(i));
}
int cnt = 0;
int x = Integer.parseInt(sb.toString());
if (x > 0 && num % x == 0) {
cnt++;
}
for (int i = k; i < s.length(); i++) {
sb.deleteCharAt(0);
sb.append(s.charAt(i));
x = Integer.parseInt(sb.toString());
if (x > 0 && num % x == 0) {
cnt++;
}
}
return cnt;
}
2.4 类似题型
1456.定长子串中元音的最大数目
2379.得到K个黑块的最少涂色次数1
343. 大小为 K 且平均值大于等于阈值的子数组数目
2090.半径为 k 的子数组平均值
3. 找到字符串中所有字母异位词(中等)
3.1 题目描述
3.2 解题思路
典型的滑动窗口思路,题目中所谓的异位词,实际上就是指统计窗口内出现的每个字符个数是否一致即可。
常见的统计字符个数的方式可以通过数组下标计数来解决
3.3 代码实现
public List<Integer> findAnagrams(String s, String p) {
int sLen = s.length(), pLen = p.length();
if (sLen < pLen) {
return 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']++;
}
List<Integer> ans = new ArrayList<>();
if (Arrays.equals(sCount, pCount)) {
ans.add(0);
}
for (int i = 0; i < sLen - pLen; i++) {
sCount[s.charAt(i) - 'a']--;
sCount[s.charAt(i + pLen) - 'a']++;
if (Arrays.equals(sCount, pCount)) {
ans.add(i + 1);
}
}
return ans;
}
4. 可获得的最大点数(简单)
4.1 题目描述
4.2 解题思路
4.3 代码实现
public int maxScore(int[] cardPoints, int k) {
int sum = 0;
for (int i = 0; i < k; i++) {
sum += cardPoints[i];
}
int maxSum = sum;
for (int i = 1; i < k; i++) {
sum = sum - cardPoints[k - i] + cardPoints[cardPoints.length - i];
maxSum = Math.max(maxSum, sum);
}
return maxSum;
}
5. 最少交换次数来组合所有的1 II(中等)
5.1 题目描述
5.2 解题思路
先统计一下一共有多少个1,然后同样是按照环形数组的处理方式来滑动窗口,每个窗口的交换次数即:1的总数减去窗口内1的个数。
5.3 代码实现
public int minSwaps(int[] nums) {
int total1 = 0;
for (int num : nums) {
if (num == 1) {
total1++;
}
}
int sum = 0;
for (int i = 0; i < total1; i++) {
sum += nums[i];
}
int min = total1 - sum;
for (int i = 1; i < nums.length; i++) {
int a = nums[i - 1];
int b = nums[(i + total1 - 1) % nums.length];
sum = sum - a + b;
min = Math.min(min, total1 - sum);
}
return min;
}
6. 长度为K的子数组中的最大和(中等)
6.1 题目描述
6.2 解题思路
一样的滑动窗口的思路,然后借助Hash表来辅助判断滑动的窗口中是否存在重复即可。
6.3 代码实现
public long maximumSubarraySum(int[] nums, int k) {
long sum = 0;
Map<Integer, Integer> map = new HashMap<>();
for (int i = 0; i < k; i++) {
map.put(nums[i], map.getOrDefault(nums[i], 0) + 1);
sum += nums[i];
}
long ans = 0;
if (map.size() >= k) {
ans = sum;
}
for (int i = k; i < nums.length; i++) {
int x = nums[i];
int y = nums[i - k];
Integer n = map.get(y);
if (n - 1 == 0) {
map.remove(y);
} else {
map.put(y, n - 1);
}
map.put(x, map.getOrDefault(x, 0) + 1);
sum = sum - y + x;
if (map.size() >= k) {
ans = Math.max(ans, sum);
}
}
return ans;
}
6.4 类似题型
7. 学生分数的最小差值(简单)
7.1 题目描述
7.2 解题思路
前面几题都是枚举窗口的结束为止,然后不断改变窗口的开始位置,本题可以看作是枚举窗口的开始位置,然后不断改变的窗口的结束位置。
7.3 代码实现
public int minimumDifference(int[] nums, int k) {
Arrays.sort(nums);
int diff = nums[k - 1] - nums[0];
for (int i = 1; i < nums.length - k + 1; i++) {
diff = Math.min(diff, nums[i + k - 1] - nums[i]);
}
return diff;
}
8. 爱生气的书店老板(简单)
8.1 题目描述
8.2 解题思路
同类题,可以先统计所有不生气的用户满意度总和,然后再利用滑动窗口来解决,只是需要额外处理一下窗口内原来就是不生气的情况。
8.3 代码实现
public int maxSatisfied(int[] customers, int[] grumpy, int minutes) {
int totalNoGrumpy = 0;
for (int i = 0; i < customers.length; i++) {
if (grumpy[i] == 0) {
totalNoGrumpy += customers[i];
}
}
int sum = 0;
for (int i = 0; i < minutes; i++) {
// grumpy[i]为0来处理已经统计过的情况。
sum += customers[i] * grumpy[i];
}
int maxSum = sum;
for (int i = minutes; i < customers.length; i++) {
sum = sum - (customers[i - minutes] * grumpy[i - minutes]) + (customers[i] * grumpy[i]);
maxSum = Math.max(maxSum, sum);
}
return totalNoGrumpy + maxSum;
}