209. 长度最小的子数组

 思路:滑动窗口法

受到 76 题 Minimum Window Substring 的启示,找一个范围使得其值满足某个条件,然后就会想到滑动窗口,也就是用双指针的方法。和这道题本质是一样的。

用双指针 left 和 right 表示一个窗口。

(1)ight 向右移增大窗口,直到窗口内的数字和大于等于了 s。进行第 2 步。
(2)记录此时的长度,left 向右移动,开始减少长度,每减少一次,就更新最小长度。直到当前窗口内的数字和小于了 s,回到第 1 步。
举个例子,模拟下滑动窗口的过程吧。

s = 7, nums = [2,3,1,2,4,3]

2 3 1 2 4 3
^
l
r
上边的窗口内所有数字的和 2 小于 7, r 右移

2 3 1 2 4 3
^ ^
l r
上边的窗口内所有数字的和 2 + 3 小于 7, r 右移

2 3 1 2 4 3
^   ^
l   r
上边的窗口内所有数字的和 2 + 3 + 1 小于 7, r 右移

2 3 1 2 4 3
^     ^
l     r
上边的窗口内所有数字的和 2 + 3 + 1 + 2 大于等于了 7, 记录此时的长度 min = 4, l 右移

2 3 1 2 4 3
  ^   ^
  l   r
上边的窗口内所有数字的和 3 + 1 + 2  小于 7, r 右移

2 3 1 2 4 3
  ^     ^
  l     r
上边的窗口内所有数字的和 3 + 1 + 2 + 4 大于等于了 7, 更新此时的长度 min = 4, l 右移

2 3 1 2 4 3
    ^   ^
    l   r
上边的窗口内所有数字的和 1 + 2 + 4 大于等于了 7, 更新此时的长度 min = 3, l 右移

2 3 1 2 4 3
      ^ ^
      l r
上边的窗口内所有数字的和 2 + 4 小于 7, r 右移

2 3 1 2 4 3
      ^   ^
      l   r
上边的窗口内所有数字的和 2 + 4 + 3 大于等于了 7, 更新此时的长度 min = 3, l 右移

2 3 1 2 4 3
        ^ ^
        l r
上边的窗口内所有数字的和 4 + 3 大于等于了 7, 更新此时的长度 min = 2, l 右移

2 3 1 2 4 3
          ^
          r
          l
上边的窗口内所有数字的和 3 小于 7, r 右移,结束

作者:windliang
链接:https://leetcode-cn.com/problems/minimum-size-subarray-sum/solution/xiang-xi-tong-su-de-si-lu-fen-xi-duo-jie-fa-by-43/
来源:力扣(LeetCode)
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。

  

class Solution {
    public int minSubArrayLen(int s, int[] nums) {
        int n=nums.length;
        int slow=0;//左边界
        int quick=0;//右边界
        int sum=0;//窗口里数字总和
        int min=Integer.MAX_VALUE;//当前满足条件的连续子数组的长度
        while(quick<n)
        {
            sum+=nums[quick];//滑动窗口右侧往右移动
             quick++;
             while(sum>=s)//当遇到窗口内数字总和大于等于s,记录此时的滑动窗口大小,把窗口左边往右移
             {
                min = Math.min(min, quick - slow);//这里写quick-slow的原因是,这个while之外,quick已经有了一个自增的过程,自增后的quick-slow正好是长度,不需要再加一了
                sum -= nums[slow];
                slow++;
             }
        }
        return min == Integer.MAX_VALUE ? 0 : min;
    }
}

  

原文地址:https://www.cnblogs.com/lzh1043060917/p/12963336.html