Leetcode - 滑动窗口

1. 滑动窗口

1. 滑动窗口的大概思想如下：

1. 可以通过两个指针来标识窗口的边界。
2. 窗口的长度是可以固定的，也可以是可变的，完全取决于求解的问题性质。
3. 维护一个或者一组和窗口相关联的状态变量，能有效降低计算量和算法复杂度。

2. 算法思想:什么是滑动窗口？

其实就是一个队列,比如例题中的 abcabcbb，进入这个队列（窗口）为 abc 满足题目要求，当再进入a，队列变成了 abca，这时候不满足要求。所以，我们要移动这个队列
如何移动？我们只要把队列的左边的元素移出就行了，直到满足题目要求

2. 举例

下面例子采用语言JAVA

2.1 无重复字符的最长子串

无重复字符的最长子串

class Solution {public int lengthOfLongestSubstring(String s) {int[] last = new int[128];for(int i = 0; i < 128; i++) {last[i] = -1;}int res = 0;int start = 0; // 窗口开始位置int n = s.length();for(int i = 0; i < s.length(); i++) {int index = s.charAt(i);start = Math.max(start, last[index]);//last[index]代表上一次出现的位置，但是字符串内字符不能重复，所以要从上一次出现位置的下一个位置开始//last[index]的存在是为了使得窗口滑动到下一个位置res   = Math.max(res, i - start + 1);//当前字符串个数 = 数据末指针-窗口初始位置+1last[index] = i+1;//窗口的下一个位置赋值}return res;}
}

2.2 长度最小的子数组

长度最小的子数组 && 参考文档

class Solution {public int minSubArrayLen(int target, int[] nums) {int i=0,j=0,sum=0,min = Integer.MAX_VALUE;while(i<nums.length){sum = sum +nums[i++];while(sum >= target){min = Math.min(min,i-j);sum = sum - nums[j++];}}return min == Integer.MAX_VALUE ? 0 : min;}
}

2.3 滑动窗口最大值

滑动窗口最大值

class Solution {public int[] maxSlidingWindow(int[] nums, int k) {int length = nums.length;int i = 0,j = 0;int out = length-k+1;//外循环次数 int []arr = new int[out];for(i = 0; i<out ; i++){int max = Integer.MIN_VALUE;for(j = i; j<i+k ; j++){max = Math.max(max,nums[j]);}arr[i] = max;}return arr;}
}

2.4 最小覆盖子串

最小覆盖子串 && 参考文旦

class Solution {public String minWindow(String s, String t) {HashMap<Character,Integer> hs = new HashMap<Character,Integer>();HashMap<Character,Integer> ht = new HashMap<Character,Integer>();for(int i = 0;i < t.length();i ++){ht.put(t.charAt(i),ht.getOrDefault(t.charAt(i), 0) + 1);}String ans = "";int len = 1000000, cnt = 0;  for(int i = 0,j = 0;i < s.length();i ++){hs.put(s.charAt(i), hs.getOrDefault(s.charAt(i), 0) + 1);if(ht.containsKey(s.charAt(i)) && hs.get(s.charAt(i)) <= ht.get(s.charAt(i))) cnt ++;while(j < i && (!ht.containsKey(s.charAt(j)) || hs.get(s.charAt(j)) > ht.get(s.charAt(j)))){int count = hs.get(s.charAt(j)) - 1;hs.put(s.charAt(j), count);j ++;}if(cnt == t.length() && i - j + 1 < len){len = i - j + 1;ans = s.substring(j,i + 1);}}return ans;}
}

2.5 删除有序数组中的重复项

删除有序数组中的重复项

class Solution {public int removeDuplicates(int[] nums) {int n = nums.length;if(n == 0) return 0;int fast = 1, slow = 1;while (fast < n) {if (nums[fast] != nums[fast - 1]) {nums[slow] = nums[fast];slow ++;}fast ++;}return slow;}
}