江门制作手机网站,塘厦房价,答辩ppt模板免费下载 素材,做哈尔滨本地门户网站赚钱吗文章目录 1. 滑动窗口2. 举例2.1 无重复字符的最长子串2.2 长度最小的子数组2.3 滑动窗口最大值2.4 最小覆盖子串2.5 删除有序数组中的重复项 1. 滑动窗口
滑动窗口的大概思想如下#xff1a; 可以通过两个指针来标识窗口的边界。窗口的长度是可以固定的#xff0c;也可以是… 文章目录 1. 滑动窗口2. 举例2.1 无重复字符的最长子串2.2 长度最小的子数组2.3 滑动窗口最大值2.4 最小覆盖子串2.5 删除有序数组中的重复项 1. 滑动窗口
滑动窗口的大概思想如下 可以通过两个指针来标识窗口的边界。窗口的长度是可以固定的也可以是可变的完全取决于求解的问题性质。维护一个或者一组和窗口相关联的状态变量能有效降低计算量和算法复杂度。 算法思想:什么是滑动窗口 其实就是一个队列,比如例题中的 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] i1;//窗口的下一个位置赋值}return res;}
}2.2 长度最小的子数组
长度最小的子数组 参考文档
class Solution {public int minSubArrayLen(int target, int[] nums) {int i0,j0,sum0,min Integer.MAX_VALUE;while(inums.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-k1;//外循环次数 int []arr new int[out];for(i 0; iout ; i){int max Integer.MIN_VALUE;for(j i; jik ; j){max Math.max(max,nums[j]);}arr[i] max;}return arr;}
}2.4 最小覆盖子串
最小覆盖子串 参考文旦
class Solution {public String minWindow(String s, String t) {HashMapCharacter,Integer hs new HashMapCharacter,Integer();HashMapCharacter,Integer ht new HashMapCharacter,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;}
}
