LeetCode探索（滑动窗口）

模板

滑动窗口一般用在字符串匹配、寻找子序列和等题目中。
其实滑动窗口就是双指针的特殊场景。
我们来回忆一下滑动窗口的题目一般是如何应用的。
我们需要先移动右指针，然后看是否需要进行收缩窗口。如果需要的话则不断移动左指针然后进行收缩，直至不满足收缩条件。

int left=0,right=0;
while(right <　s.size()){
	windows.add(s[right])
	right++;
	while(window needs shrink){
		window.remove(s[left]);
		left++;
	}
}

代码来源于：https://labuladong.gitbook.io/algo/suan-fa-si-wei-xi-lie/hua-dong-chuang-kou-ji-qiao-jin-jie

长度最小的子数组

题目：https://leetcode-cn.com/problems/minimum-size-subarray-sum/
题目大意：给定一个含有 n 个正整数的数组和一个正整数 s ，找出该数组中满足其和 ≥ s 的长度最小的连续子数组，并返回其长度。如果不存在符合条件的连续子数组，返回 0。
分析：
这道题其实有两种做法：前缀和+二分、滑动窗口。

使用前缀和的做法就是首先计算出一个前缀和数组，然后对于任意前缀和大于等于s的元素，我们通过二分查找出一个前缀和使得sum[i]-sum[j]恰好大于等于s，并且记录此时的长度，最后返回一个最小长度。
这样的时间效率是o(nlogn)，不需要额外空间。

如果使用滑动窗口的话则时间效率更高，能够达到o(n)。我们采用上面的模板尝试带入一下，首先要确定什么时候窗口进行收缩？
当和大于等于s的时候我们就需要进行收缩了，那么什么时候停止收缩呢？也很容易得知当和小于s的就停止收缩，所以得出代码：

class Solution {
    public int minSubArrayLen(int s, int[] nums) {
        if(nums == null || nums.length == 0)
            return 0;
        int start = 0;
        int end = 0;
        int min = nums.length+1;
        int sum = 0;
        while(end < nums.length){
        	//计算和，并且把nums[end]加入窗口
            sum += nums[end++];
            //需要收缩
            while(sum >= s){
            	//此时满足条件，记录最小值
                min = Math.min(min,end-start);
                //收缩，将nums[start]移除窗口，并start++
                sum -= nums[start++];
            }
        }
        return min == nums.length+1? 0 : min;
    }
}

无重复字符串的最长子串

题目：https://leetcode-cn.com/problems/longest-substring-without-repeating-characters/
题目大意：给定一个字符串，请你找出其中不含有重复字符的最长子串的长度。
分析：
同样的，我们来思考一下什么时候需要进行收缩，如何进行收缩？
我们首先采用一个hashMap记录上一次字符出现的位置，然后当右侧指针指向的字符加入窗口之后查看当前窗口内是否包含了这个字符，如果包含了这个字符则需要进行收缩。
那么如何判断是否包含上次出现的字符呢？我们只需要判断一下左指针是否大于hashmap中存放的值就可以了，如果大于则说明不包含，如果小于则说明包含。
确定了需要收缩之后，那么如何进行收缩呢？直接将左指针移动到上次字符出现的位置后面一位就可以了。

class Solution {
    public int lengthOfLongestSubstring(String s) {
        if(s == null || s.length() == 0)
            return 0;
        int left = 0,right = 0;
        HashMap<Character,Integer> map = new HashMap<>();
        int max = 0;
        while(right < s.length()){
            char c = s.charAt(right);
            //收缩窗口，这里由于可以一次收缩到位所以不需要while
            if(map.containsKey(c) && map.get(c) >= left){
                left = map.get(c)+1;
            }
            map.put(c,right);
            right++;
            max = Math.max(max,right-left);
        }
        return max;
    }
}