滑动窗口

1. 应用场景

关键词：

1. 满足XXX条件（计算结果，出现次数，同时包含）
2. 最长/最短
3. 子串/子数组/子序列

Eg：长度最小的子数组

2. 使用思路

1. 寻找最长

左右双指针（L，R）在起始点，R向右逐位滑动循环

——每次滑动过程中

• 窗内元素满足条件，R向右扩大窗口，并更新最优结果
• 窗内元素不满足条件，L向右缩小窗口

——R到达结尾

2. 模版

1. 初始化 left, right,  currentResult, bestResult
2. while (右指针没有到达结尾) {
     加入right对应元素的值，更新currentResult
     while (currentResult 不满足要求) {
        1 窗口缩小，left右移 left++;
    }
    1》更新最优结果 bestResult
    2》窗口扩大 right右移 right++;
   }
3. 返回bestResult

3. 例题

给定一个字符串 s ，请你找出其中不含有重复字符的 最长 子串 的长度。

public class MaxLengthOfSubString {
    public static int maxLengthOfSubString(String s) {
        if (s.length() == 0) {
            return 0;
        }
        int left = 0;
        int right = 0;
        HashMap<Character, Integer> map = new HashMap();

        for (int i = 0; i < s.length(); i++) {
            if (map.containsKey(s.charAt(i))) {
                left = Math.max(left, map.get(s.charAt(i)) + 1);
            }
            map.put(s.charAt(i), i);
            right = Math.max(right, i - left + 1);
        }
        return right;
    }

    public static void main(String[] args) {
        String s = "abcabcbb";
        int i = maxLengthOfSubString(s);
        System.out.println(i);
    }
}

2. 寻找最短

左右双指针（L，R）在起始点，R向右逐位滑动循环

——每次滑动过程中

• 窗内元素满足条件，L向右缩小窗口，并更新最优结果
• 窗内元素不满足条件，R向右扩大窗口

——R到达结尾

2. 模版

1. 初始化 left, right,  currentResult, bestResult
2. while (右指针没有到达结尾) {
     加入right对应元素的值，更新currentResult
     while (currentResult 满足要求) {
        1》更新最优结果 bestResult
        2》移除left对应元素的值
        3》窗口缩小，left右移 left++;
    }
    窗口扩大 right右移 right++;
   }
3. 返回bestResult

3. 例题

给定一个含有 n 个正整数的数组和一个正整数 target 。

找出该数组中满足其总和大于等于 target 的长度最小的 连续

子数组

[numsl, numsl+1, ..., numsr-1, numsr] ，并返回其长度。如果不存在符合条件的子数组，返回 0 。

class Solution {
    public int minSubArrayLen(int target, int[] nums) {
     int left = 0;
        int right = 0;
        int minLength = Integer.MAX_VALUE;
        int curSum = 0;

        int sLength = nums.length;
        if (sLength == 0) {
            return 0;
        }
        while (right < sLength) {
            curSum += nums[right];
            while (curSum >= target) {
                minLength = Math.min(minLength, right - left + 1);
                curSum -= nums[left];
                left++;
            }
            right++;
        }
        return minLength == Integer.MAX_VALUE ? 0: minLength;
    }   
}