当前位置：首页 > web >正文

滑动窗口 -- 灵神刷题

web 2025/7/13 9:48:15

元素都是正数，并且求数量一般都是可以使用滑动窗口

长度最小的子数组

https://leetcode.cn/problems/minimum-size-subarray-sum/description/

class Solution {public int minSubArrayLen(int target, int[] nums) {int left = 0;//滑动窗口的左边界int res = nums.length+1,ans = 0;for(int right = 0;right<nums.length;++right){ans+=nums[right];   while(ans>=target){res = Math.min(res,right-left+1);ans -=nums[left++];}}return res==nums.length+1?0:res;}
}

无重复字符的最长子串

https://leetcode.cn/problems/longest-substring-without-repeating-characters/description/

可以使用数组使用哈希表写起来也是比较复杂的


class Solution {public int lengthOfLongestSubstring(String s) {Map<Character,Integer> count = new HashMap<>();int res = 0;int left = 0;for(int i = 0;i<s.length();++i){Character c = s.charAt(i);count.put(c,count.getOrDefault(c,0)+1);while(count.get(c)>1){count.put(s.charAt(left),count.get(s.charAt(left))-1);++left;}res = Math.max(res,i-left+1);}return res;}
}

乘积小于 K 的子数组

https://leetcode.cn/problems/subarray-product-less-than-k/description/

这里我们right-left+1就是以right位置元素为结尾的符合条件的个数

class Solution {public int numSubarrayProductLessThanK(int[] nums, int k) {if(k==0||k==1)return 0;int res = 0,ans = 1;int left = 0;for(int right = 0;right<nums.length;++right){ans*=nums[right];while(ans>=k){ans/=nums[left];++left;}res += right-left+1;}return res;}
}

最多 K 个重复元素的最长子数组

https://leetcode.cn/problems/length-of-longest-subarray-with-at-most-k-frequency/description/

滑动窗口：该算法使用双指针（left和right）维护一个动态窗口，确保窗口中每个数字的出现次数不超过k。
HashMap的作用：实时统计窗口中每个数字的出现次数，当某个数字的计数超过k时，移动左边界直到计数合法。
时间复杂度：O(n)，其中n为数组长度，每个元素最多被遍历两次（right和left各一次）。

class Solution {public int maxSubarrayLength(int[] nums, int k) {int res = 0; // 存储最终结果（最长子数组长度）Map<Integer,Integer> map = new HashMap<>(); // 记录每个数字在当前窗口的出现次数int left = 0, n = nums.length; // 滑动窗口的左边界和数组长度for(int right = 0; right < n; ++right) {int num = nums[right];map.merge(num, 1, Integer::sum); // 更新当前数字的计数（增加1）// 当当前数字的计数超过k时，移动左边界缩小窗口while(map.get(num) > k) {map.merge(nums[left], -1, Integer::sum); // 减少左边界数字的计数left++; // 左边界右移}// 更新最大子数组长度（当前窗口大小：right - left + 1）res = Math.max(res, right - left + 1);}return res;}
}

找到最长的半重复子字符串

https://leetcode.cn/problems/find-the-longest-semi-repetitive-substring/description/

class Solution {public int longestSemiRepetitiveSubstring(String s) {char[] sArr = s.toCharArray();int l = 0,res = 1;int same = 0;//移动右指针，并统计相邻相同的情况出现了多少次，记作 samefor(int r = 1;r<sArr.length;++r){if(sArr[r]==sArr[r-1])same++;if(same>1){//如果same>1，则不断移动左指针直到s[left]=s[left−1]，此时将一对相同的字符移到窗口之外。然后将 same 置为 1++l;while(sArr[l]!=sArr[l-1])++l;same = 1;}res = Math.max(res,r-l+1);}return res;}
}

最大连续1的个数 III

https://leetcode.cn/problems/max-consecutive-ones-iii/

class Solution {public int longestOnes(int[] nums, int k) {//统计0的个数 ct0  在ct0<=k 的情况下计算滑动窗口的最大值int res = 0,l = 0,ct0 = 0;for(int r=0;r<nums.length;++r){ct0 += 1-nums[r];//使用1-nums[]代替判断 这样更方便 在后面的操作更方便while(ct0>k){ct0 -= 1-nums[l];++l;}res = Math.max(res,r-l+1);}return res;}
}

统计最大元素出现至少 K 次的子数组

https://leetcode.cn/problems/count-subarrays-where-max-element-appears-at-least-k-times/description/

内层循环结束后，[left,right] 这个子数组是不满足题目要求的，但在退出循环之前的最后一轮循环，[left−1,right] 是满足题目要求的。由于子数组越长，越能满足题目要求，所以除了 [left−1,right]，还有 [left−2,right],[left−3,right],…,[0,right] 都是满足要求的。也就是说，当右端点固定在 right 时，左端点在 0,1,2,…,left−1 的所有子数组都是满足要求的，这一共有 left 个，加到答案中

class Solution {public long countSubarrays(int[] nums, int k) {int max = 0;for(int num:nums){max= Math.max(max,num);}int l = 0,maxNums = 0;long res = 0;for(int r = 0;r<nums.length;++r){if(nums[r]==max)++maxNums;while(maxNums==k){if(nums[l]==max)--maxNums;++l;}//循环完之后[l,r]不符合要求 但是[l-1,r] ... [0,r]都是符合的res+=l;}return res;}
}

统计得分小于 K 的子数组数目

https://leetcode.cn/problems/count-subarrays-with-score-less-than-k/description/

越短越合法

class Solution {public long countSubarrays(int[] nums, long k) {int l = 0;long sum = 0,res =0;for(int r=0;r<nums.length;++r){sum+=nums[r];while(sum*(r-l+1)>=k){sum-=nums[l];++l;}res+=r-l+1;}return res;}
}

将 x 减到 0 的最小操作数

https://leetcode.cn/problems/minimum-operations-to-reduce-x-to-zero/

逆向思维+滑动窗口

把问题转换成「从 nums 中移除一个最长的子数组，使得剩余元素的和为 x」。

class Solution {public int minOperations(int[] nums, int x) {int target = -x;for(int num:nums){target+=num;}//这里target+x == nums的所有数的和  我们从nums找到多少个可以等于target 那么剩下的就是等于x的if(target<0)return -1;int l=0,sum=0,res=-1;for(int r=0;r<nums.length;++r){sum+=nums[r];while(sum>target){sum-=nums[l];++l;}if(sum==target){res = Math.max(res,r-l+1);//尽可能使达到target的长度越长 那么达到x的长度就越短}}return res<0?-1:nums.length-res;}
}

最小覆盖子串

https://leetcode.cn/problems/minimum-window-substring/

class Solution {public String minWindow(String s, String t) {int llen = s.length(),slen=t.length();if(llen<slen)return "";int[] cntS = new int[128]; // s 子串字母的出现次数int[] cntT = new int[128]; // t 中字母的出现次数for(char c:t.toCharArray()){cntT[c]++;}int l=0,count=0,len = llen+1;String res="";for(int r=0;r<llen;++r){cntS[s.charAt(r)]++; // 右端点字母移入子串while(isCovered(cntS,cntT)){if(len>(r-l+1)){len = r-l+1;res = s.substring(l,r+1);}cntS[s.charAt(l)]--; // 左端点字母移出子串++l;}}return res;}private boolean isCovered(int[] cntS, int[] cntT) {for (int i = 'A'; i <= 'Z'; i++) {if (cntS[i] < cntT[i]) {return false;}}for (int i = 'a'; i <= 'z'; i++) {if (cntS[i] < cntT[i]) {return false;}}return true;}
}