滑动窗口
滑动窗口是指在数组、字符串、链表等线性结构上的一段，类似一个窗口，而这个窗口可以依次在上述线性结构上从头到尾滑动，且窗口的首尾可以收缩。我们在处理滑动窗口的时候，常用双指针来解决，左指针维护窗口左界，右指针维护窗口右界，二者同方向不同速率移动维持窗口。
最长不含重复字符的子符串
题目链接:最长不含重复字符的子字符串
既然要找一段连续子串的内不重复的长度，我们可以使用滑动窗口，保证窗口内都是不重复的，然后窗口右界不断向右滑，如果窗口内出现了重复字符，说明新加入的元素与之前的重复了，只需要窗口左界也向右收缩就可以保证窗口内都是不重复的。
而保证窗口内的元素不重复，我们可以使用根据key值快速访问的哈希表，key值为窗口内的元素，value为其出现次数，只要新加入窗口的元素出现次数不为1，就是重复。
这里使用哈希表因为哈希表可以在0(1)时间内找到value!
import java.util.*; public class Solution { /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * * * @param s string字符串 * @return int整型 */ public int lengthOfLongestSubstring (String s) { // write code here //滑动窗口! //left right控制左右窗口边界! //hashmap 记录窗口内支付出现次数! //如果右边界right字符出现次数不为1 //说明重复,left右移窗口缩小!并且这个元素的出现次数减一! //否则right右移! HashMap<Character,Integer> table = new HashMap<>(); int max = 0; for(int left = 0,right = 0;right<s.length();right++){ if(table.containsKey(s.charAt(right))){ //table表中记录的这个字符 //这个字符的次数加一! table.put(s.charAt(right),table.get(s.charAt(right))+1); }else{ //否则这里记录该字符! table.put(s.charAt(right),1); } while(table.get(s.charAt(right))>1){ //出现次数大于1窗口右移缩小 table.put(s.charAt(left),table.get(s.charAt(left++))-1); } max = Math.max(max,right-left+1); } return max; } }
和为S的连续正数序列
题目链接
滑动窗口
初始条件从[1,2]开始,结束标志r>=l
相等就滑动l++,r++
tmp<sum窗口扩大,右边界右移,tmp>sum窗口变小,左边界右移
这里的窗口想象成从左到右窗口宽度递增!
import java.util.ArrayList; public class Solution { public ArrayList<ArrayList<Integer> > FindContinuousSequence(int sum) { //滑动窗口! // sum 9 [2,3,4],[4,5] //从1,2开始,然后向左右两边扩大窗口边界! // 如果满足相等保存就保存! ArrayList<ArrayList<Integer>> result = new ArrayList<>(); for(int l = 1,r = 2;l<r;){//循环结束 l>=r! int tmp = (l+r)*(r-l+1)/2;//等差数列求和! if(tmp==sum){//相等就滑动窗口! ArrayList<Integer> arr = new ArrayList<>(); for(int i = l;i<=r;i++){ arr.add(i); } result.add(arr); //相等就滑动窗口! l++;r++; }else if(tmp<sum){//需要右边界扩大! r++; }else{//左边缩小! l++; } } return result; } }
