【Leetcode】滑动窗口合集

209.长度最小的子数组

题目

思路

1. 因为数组中的数字都是正数,所以我们可以利用单调性使用滑动窗口的方式来实现
2. 用两个指针left和right维护一段区间 当right向右移动时,这个区间内的和增大,当left向右移动时,这个区间内的和减少,这就是这道题目的单调性,我们就可以利用单调性来解题

代码

class Solution {public int minSubArrayLen(int target, int[] nums) {int sum = 0;int ret = Integer.MAX_VALUE;for(int left = 0, right = 0; right < nums.length; right++){sum += nums[right];//如果窗口内元素大于target此时就要移动left指针,直到窗口内值小于target,并且过程中不断更新结果while(sum >= target){ret = Math.min(ret,right - left + 1);sum -= nums[left++];}}return ret == Integer.MAX_VALUE ? 0 : ret;}
}

3. 无重复字符的最长子串（medium）

题目

思路

1. 利用滑动窗口维护一个区间来找最长字串,利用哈希表来检查是否有重复元素
2. 创建left指针和right指针,right指针每次向后走,就将当前位置的字符放在哈希表中,如果,此时这个元素在哈希表中出现次数超过一次,就移动left指针,每次移动left指针都要将left指针所指向的位置的元素删除,直到这个元素只出现一次,再次移动right指针

class Solution {public int lengthOfLongestSubstring(String s) {int[] hash = new int[128];//数组模拟哈希表int ret = 0;char[] arr = s.toCharArray();for(int left = 0, right = 0; right < s.length(); right++){hash[arr[right]]++;//每次将right位置的元素放在哈希表中while(hash[arr[right]] > 1){//当放进去的元素重复时,就开始移动左指针删除做指针指向的元素hash[arr[left++]]--;}ret = Math.max(ret,right-left+1);}return ret;}
}

11. 最大连续 1 的个数 III

题目

思路

1. 根据题意翻转0,我们可以将问题转化为数组中最长的不超过k个0的序列
2. 此时根据滑动窗口就可以很好的解决这道题目

class Solution {public int longestOnes(int[] nums, int k) {int cnt = 0;int ret = 0;for(int left = 0,right = 0; right < nums.length; right++){//如果进窗口的元素是0,则0计数器+1if(nums[right] == 0){cnt++;}//此时窗口中0的个数超出了要求,移动左指针left调整窗口,使其符合题意while(cnt == k + 1){if(nums[left++] == 0){cnt--;}}ret = Math.max(ret,right-left+1);}return ret;}
}

1658. 将 x 减到 0 的最⼩操作数

题目

思路

1. 这道题通过题意,可以转化为和为sum-x的最大子数组
2. 使用滑动窗口来解决此题

代码

class Solution {public int minOperations(int[] nums, int x) {int sum = 0;for(int i = 0;i < nums.length; i++){sum += nums[i];}int k = sum - x;if(k < 0){return -1;}int ret = -1;sum = 0;for(int left = 0, right = 0; right < nums.length; right++){sum += nums[right];while(sum > k){sum -= nums[left++];}if(sum == k){ret = Math.max(ret,right - left + 1);}}if(ret == -1){return -1;}return nums.length - ret;}
}

904. 水果成篮

题目

思路

1. 题目已经暗示我们使用滑动窗口来解决问题,把问题转化成最长的只有两种数字的字串
2. 通过哈希表的方式来记录是否超出种类

代码

class Solution {public int totalFruit(int[] fruits) {Map<Integer,Integer> hash = new HashMap<>();int ret = 0;for(int left = 0, right = 0; right < fruits.length; right++){hash.put(fruits[right],hash.getOrDefault(fruits[right],0) + 1);while(hash.size() > 2){hash.put(fruits[left],hash.get(fruits[left]) -1);if(hash.get(fruits[left]) == 0){hash.remove(fruits[left]);}left++;}ret = Math.max(ret,right - left + 1);}return ret;}
}

438.找到字符串中所有字母的异位词

题目

思路

1. 通过滑动窗口的方式,窗口大小恒为p字符串的长度,用哈希表分别存放两个字符串的每个字符,如果两个哈希表相同,则将这个窗口左下标放在结果集中

代码

class Solution {public List<Integer> findAnagrams(String s, String p) {List<Integer> ret = new ArrayList<>();Map<Character,Integer> start = new HashMap<>();Map<Character,Integer> end = new HashMap<>();for(int i = 0; i < p.length(); i++){start.put(p.charAt(i),start.getOrDefault(p.charAt(i), 0) + 1);}for(int left = 0, right = 0; right < s.length(); right++){end.put(s.charAt(right),end.getOrDefault(s.charAt(right), 0) + 1);if(right - left + 1 == p.length()){if(start.equals(end)){ret.add(left);if(end.get(s.charAt(left)) == 1){end.remove(s.charAt(left));}else {end.put(s.charAt(left),end.getOrDefault(s.charAt(left), 0) - 1);}}else{end.put(s.charAt(left),end.getOrDefault(s.charAt(left), 0) - 1);if(end.get(s.charAt(left)) == 0){end.remove(s.charAt(left));}}left++;}}return ret;}
}