【滑动窗口】之 长度最小的子数组

209. 长度最小的子数组

暴力循环法：

  public int minSubArrayLen(int target, int[] nums) {
        int min = Integer.MAX_VALUE;
        for (int i = 0; i < nums.length; i++) {
            int sum = nums[i];
            //只要有个元素 ＞ 目标值 就返回最小长度1
            if (sum >= target) {
                return 1;
            }
            for (int j = i + 1; j < nums.length; j++) {
                sum += nums[j];
                if (sum >= target) {
                    min = Math.min(min, j - i + 1);
                    break;//终止本次内循环 相当于left指针右移
                }
            }
        }
        return min == Integer.MAX_VALUE ? 0 : min;
    }
执行用时：150 ms, 在所有 Java 提交中击败了6.65%的用户
内存消耗：41.4 MB, 在所有 Java 提交中击败了24.27%的用户

滑动窗口：使用队列相加（实际上我们也可以把它称作是滑动窗口，这里的队列其实就相当于一个窗口）

①我们把数组中的元素不停的入队，直到总和大于等于 s 为止，接着记录下队列中元素的个数；

②然后再不停的出队，直到队列中元素的和小于 s 为止

③接着再把数组中的元素添加到队列中……重复上面的操作，直到数组中的元素全部使用完为止。
这里以 [2,3,1,2,4,3] 举例画个图来看下

上面画的是使用队列，但在代码中我们不直接使用队列，我们使用两个指针，刚开始都指向队头；

 public int minSubArrayLen(int target, int[] nums) {
        int min = Integer.MAX_VALUE;
        int left=0,right=0;//left相当于出队，right相当于入队
        int sum=0;
        //当右指针指向队尾就结束
        while (right<nums.length){
            sum+=nums[right++];
            while (sum>=target){
                min=Math.min(min,right-left);//这里为什么不加一因为到下一行right已经+=1了
                sum-=nums[left];//队首出队
                left++;
            }
        }
        return min == Integer.MAX_VALUE ? 0 : min;
    }