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

滑动窗口

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

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

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

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