LeetCode-数组-定长滑动窗口-中等难度

滑动窗口

一般我们在学习滑动窗口时，可以把它分为定长与不定长来针对性练习，滑动窗口实际上也可以看作是双指针，尤其是不定长的滑动窗口，本篇文章主要整理了一些比较有代表性的定长类滑动窗口的题型，以供练习。

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 类似题型

2841.几乎唯一子数组的最大和

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;
}