LeetCode-数组-滑动窗口-中等难度
站长
· 阅读数 3
前言
滑动窗口经常会用来解决数组中的问题，通常可以分为定长滑动窗口与非定长滑动窗口，定长滑动窗口相对比较简单，而非定长滑动窗口也可以理解为就是双指针，相对复杂一些。
定长滑动窗口
1. 子数组最大平均数 I（简单）
题目描述
解题思路
代码实现
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;
}
leetcode跳转：子数组最大平均数
2. 找到一个数字的 K 美丽值（简单）
题目描述
解题思路
与第一题解题思路是一样的
代码实现
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;
}
leetcode跳转：找到一个数字的K美丽值
2.1. 类似题型
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;
}
3.1. 类似题型
4. 可获得的最大点数（中等）
题目描述
解题思路
看成一个环形数组，之后就与前面几题思路一致了。
代码实现
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（中等）
题目描述
解题思路
先统计一下一共有多少个1，然后同样是按照环形数组的处理方式来滑动窗口，每个窗口的交换次数即：1的总数减去窗口内1的个数。
代码实现
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的子数组中的最大和（简单）
题目描述
解题思路
一样的滑动窗口的思路，然后借助Hash表来辅助判断滑动的窗口中是否存在重复即可。
代码实现
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.1. 类似题型
7. 学生分数的最小差值（简单）
题目描述
解题思路
前面几题都是枚举窗口的结束为止，然后不断改变窗口的开始位置，本题可以看作是枚举窗口的开始位置，然后不断改变的窗口的结束位置。
代码实现
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. 爱生气的书店老板（中等）
题目描述
解题思路
同类题，可以先统计所有不生气的用户满意度总和，然后再利用滑动窗口来解决，只是需要额外处理一下窗口内原来就是不生气的情况。
代码实现
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;
}
不定长滑动窗口
1. 无重复字符的最长子串（中等）
题目描述
解题思路
可以借助hash处理是否重复的问题，再通过双指针来框定窗口，左指针指向待移除的位置，右指针负责添加元素。
右指针移动，添加了元素{a,b}
右指针移动，添加了元素{a,b,c}，再右指针移动到下标3时，发现a已经存在了，则就会删除左指针指向的元素，因此集合就剩下了{b,c}，删除完之后，会再次尝试添加右指针指向的元素，如果还是重复则再删除左指针指向的元素，否则继续。
依次反复执行。
代码实现
public int lengthOfLongestSubstring(String s) {
Set<Character> set = new HashSet<>();
int ans = 0;
int right = 0;
int len = s.length();
for(int left = 0; left < len; left++){
if(left != 0){
set.remove(s.charAt(left - 1));
}
while(right < len && !set.contains(s.charAt(right))){
set.add(s.charAt(right++));
}
ans = Math.max(ans, right - left);
}
return ans;
}
2. 长度最小的子数组（中等）
题目描述
解题思路
几乎与上一题一样的方式
代码实现
public int minSubArrayLen(int target, int[] nums) {
int sum = 0;
int ans = Integer.MAX_VALUE;
int j = 0;
for (int i = 0; i < nums.length; i++) {
if (i > 0) {
sum -= nums[i - 1];
}
while (j < nums.length && sum < target) {
sum += nums[j];
j++;
}
if (sum >= target) {
ans = Math.min(ans, j - i);
}
}
return ans == Integer.MAX_VALUE ? 0 : ans;
}
3. 删除子数组的最大得分（中等）
题目描述
解题思路
同样的解题思路
代码实现
public int maximumUniqueSubarray(int[] nums) {
Set<Integer> set = new HashSet<>();
int right = 0;
int sum = 0;
int ans = 0;
for (int i = 0; i < nums.length; i++) {
if (i > 0) {
set.remove(nums[i - 1]);
sum -= nums[i - 1];
}
while (right < nums.length && !set.contains(nums[right])) {
set.add(nums[right]);
sum += nums[right];
right++;
}
ans = Math.max(ans, sum);
}
return ans;
}
4. 将x减到0的最小操作数（中等）
题目描述
解题思路
本题需要反过来思考，先假设全部都被移除，以[1,1,4,2,3]为例，那被移除的总和就是1+1+4+2+3=11，也就是移除了后5个元素1,1,4,2,3，显然，超过了目标值x，因此就需要少移除一点，那么我们保留第一位数1，那么被移除的总和就是1+4+2+3=10，也就是移除了后4个元素1,4,2,3，以此类推，直到移除了后2个元素2,3时得到了目标值。
当然，在整个移除的过程中，如果发现移除后的总和小于目标值，则就需要把被移除的元素加进来。
红色线框（右边范围内的元素），不断缩小，直到红色线框+黄色线框中的元素加起来不大于目标值为止
黄色线框（左边范围内的元素），不断扩大，直到红色线框+黄色线框中的元素加起来不大于目标值为止
整个过程中，如果刚好两个线框中的元素加起来等于目标值，则记录为一种移除方式，最后根据线框的范围则可比较移除元素的多少。
代码实现
public int minOperations(int[] nums, int x) {
int sum = Arrays.stream(nums).sum();
if (sum < x) {
return -1;
}
int leftSum = 0;
int rightSum = sum;
int j = 0;
int ans = Integer.MAX_VALUE;
for (int i = -1; i < nums.length; i++) {
if (i > -1) {
leftSum += nums[i];
}
while (j < nums.length && leftSum + rightSum > x) {
rightSum -= nums[j];
j++;
}
if (leftSum + rightSum == x) {
ans = Math.min(ans, i + 1 + (nums.length - j));
}
}
return ans == Integer.MAX_VALUE ? -1 : ans;
}
5. 统计完全子数组的数目（简单）
题目描述
解题思路
通过不断扩充右窗口、以及缩小左窗口的方式，统计窗口内不同元素个数。
右窗口扩充
左窗口缩小
代码实现
public int countCompleteSubarrays(int[] nums) {
Map<Integer, Integer> map = new HashMap<>();
int n = nums.length;
int ans = 0;
long cnt = Arrays.stream(nums).distinct().count();
int left = 0;
for (int i = 0; i < n; i++) {
map.put(nums[i], map.getOrDefault(nums[i], 0) + 1);
while (map.size() == cnt) {
ans += n - i;
Integer c = map.get(nums[left]);
if (c > 1) {
map.put(nums[left], c - 1);
} else {
map.remove(nums[left]);
}
left++;
}
}
return ans;
}
6. 最多K个重复元素的最长子数组（简单）
题目描述
解题思路
使用一个Hash数组用来记录窗口中每个元素出现的次数，当遍历到某个元素时，就通过Hash数组来判断改元素出现的次数是否满足条件，如果不满足则缩减左侧窗口后，再判断，直到满足为止。
代码实现
public int maxSubarrayLength(int[] nums, int k) {
Map<Integer, Integer> map = new HashMap<>();
int ans = 0;
int left = 0;
for (int i = 0; i < nums.length; i++) {
map.put(nums[i], map.getOrDefault(nums[i], 0) + 1);
while (map.get(nums[i]) > k) {
map.put(nums[left], map.get(nums[left]) - 1);
left++;
}
ans = Math.max(ans, i - left + 1);
}
return ans;
}
7. 最大连续1的个数 III（中等）
题目描述
解题思路
根据题目要求，可以转换为在满足最多包含K个0的前提下，求最长子数组的长度，这样就可以直接使用滑动窗口来解决了。
代码实现
public int longestOnes(int[] nums, int k) {
int right = 0;
int left = 0;
int n = nums.length;
int cntZero = 0;
int ans = 0;
while (right < n) {
if (nums[right] == 0) {
cntZero++;
}
while (cntZero > k) {
if (nums[left] == 0) {
cntZero--;
}
left++;
}
ans = Math.max(ans, right - left + 1);
right++;
}
return ans;
}