长度最小的子数组 ---- 滑动窗口

题目链接

题目:

分析:

• 解法一:暴力解法, 找到所有连续子数组, 保留满足条件的
• 解法二: 利用滑动窗口 找子数组 
  •  因为数组中都是正整数, 通过进窗口的操作, 我们找到一组, 如示例一中的2,3,1,2, 判断满足和>7, 那么根据单调性, 我们就不再需要判断加上后面两个数的两个子数组, 因为加上一定比7大, 并且不满足最小
  • 那么由第一个2发起的窗口就找到了最小子数组, 更新数据记录一下子数组的长度,下面我们找从下一个3开始的最小子数组,要计算3+1+2... 但是因为上一轮, 我们已经算过了2+3+1+2, 那么我们就可以直接让2出窗口, 得到一个值, 就不用重复计算了
  • 判断如果这个值<7, 说明还需要进窗口,让和变大 然后重复上述操作
  • 判断如果这个值>7, 说明还需要出窗口, 让和变小, 再进行判断

 代码:

class Solution {
    public int minSubArrayLen(int target, int[] nums) {
        int sum = 0;
        int len = Integer.MAX_VALUE;
        for(int left = 0,right = 0;right < nums.length;right++){
            //进窗口
            sum += nums[right];
            //循环判断
            while(sum >= target){
                //更新结果
                len = Math.min(len,right-left+1);
                //出窗口
                sum -= nums[left++];
            }
        }
        return len == Integer.MAX_VALUE ? 0 : len;

    }
}