滑动窗口__最长不含重复字符的子符串_和为S的连续正整数序列(剑指offer)

滑动窗口

滑动窗口是指在数组、字符串、链表等线性结构上的一段，类似一个窗口，而这个窗口可以依次在上述线性结构上从头到尾滑动，且窗口的首尾可以收缩。我们在处理滑动窗口的时候，常用双指针来解决，左指针维护窗口左界，右指针维护窗口右界，二者同方向不同速率移动维持窗口。

最长不含重复字符的子符串

题目链接:最长不含重复字符的子字符串

既然要找一段连续子串的内不重复的长度，我们可以使用滑动窗口，保证窗口内都是不重复的，然后窗口右界不断向右滑，如果窗口内出现了重复字符，说明新加入的元素与之前的重复了，只需要窗口左界也向右收缩就可以保证窗口内都是不重复的。
而保证窗口内的元素不重复，我们可以使用根据

key

值快速访问的哈希表，

key

值为窗口内的元素，

value

为其出现次数，只要新加入窗口的元素出现次数不为1，就是重复。
这里使用哈希表因为**哈希表可以在0(1)时间内找到

value

**!

importjava.util.*;publicclassSolution{/**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param s string字符串 
     * @return int整型
     */publicint lengthOfLongestSubstring (String s){// write code here//滑动窗口!//left right控制左右窗口边界!//hashmap 记录窗口内支付出现次数!//如果右边界right字符出现次数不为1//说明重复,left右移窗口缩小!并且这个元素的出现次数减一!//否则right右移!HashMap<Character,Integer> table =newHashMap<>();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窗口变小,左边界右移
• 这里的窗口想象成从左到右窗口宽度递增!

importjava.util.ArrayList;publicclassSolution{publicArrayList<ArrayList<Integer>>FindContinuousSequence(int sum){//滑动窗口! // sum 9  [2,3,4],[4,5]//从1,2开始,然后向左右两边扩大窗口边界!// 如果满足相等保存就保存!ArrayList<ArrayList<Integer>> result =newArrayList<>();for(int l =1,r =2;l<r;){//循环结束 l>=r!int tmp =(l+r)*(r-l+1)/2;//等差数列求和!if(tmp==sum){//相等就滑动窗口!ArrayList<Integer> arr =newArrayList<>();for(int i = l;i<=r;i++){
                    arr.add(i);}
                result.add(arr);//相等就滑动窗口!
             l++;r++;}elseif(tmp<sum){//需要右边界扩大!
              r++;}else{//左边缩小!
              l++;}}return result;}}