image.png

思路

• sum -= nums[i], i++ 滑动窗口的精髓在于这行代码
  遍历数组向滑动窗口中添加元素累加数值, 并每次判断是否符合条件,

1. 如果 sum < target 则一直累加sum
2. sum >= target 记录当前窗口的长度, 并更新窗口的最小长度, 因为是求连续的子数组长度, 所以先将窗口最左边的元素移除, 例[3,1,2,4] > target 移除3 剩下[1,2,4] 符合条件 更新最小长度, 如果将最左边元素移除[2,3,1,2]->[3,1,2] 任不符合条件, 窗口就继续向右边移动, 其实也就是重复的1.2步骤, 遍历到数组结束

窗口移动过程如下
[2,3,1,2,4,3]
[2,3,1,2]->[3,1,2]
[3,1,2,4] -> [1,2,4] 长度3
[2,4] ->[2,4,3]
[2,4,3] -> [4,3] 长度2
最终结果是[4,3] 最小长度是2

while (sum >= target) { // 这里如果写if 窗口就没法滑动了应该写while
  int subLen = j - i + 1;
  minLen = minLen > subLen ? subLen : minLen;
  sum -= nums[i];
  i++;
}

滑动窗口最优解 O(n)

    public static int minSubArrayLen3(int target, int[] nums) {
        int minLen = Integer.MAX_VALUE;
        int i = 0; // 滑动窗口的起始位置
        int sum = 0;
        for (int j = 0; j < nums.length ; j++) {
                sum += nums[j];
                while (sum >= target) { // 这里如果写if 窗口就没法滑动了应该写while
                    int subLen = j - i + 1; // 计算子数组长度 + 1是因为数组下标从0 开始
                    minLen = minLen > subLen ? subLen : minLen; // 每次循环更新最小长度
                    sum -= nums[i];  // 滑动窗口的精髓 更新完毕后 移除到窗口最左边的数值,方便窗口的下个回合的计算
                    i++;  // 窗口左边界也要向左滑动
                }

        }
        return minLen == Integer.MAX_VALUE ? 0 : minLen;
    }

下面是自己想的暴力解法 超时了.

    //输入：target = 7, nums = [2,3,1,2,4,3]
    public static int minSubArrayLen(int target, int[] nums) {
        int minLen = Integer.MAX_VALUE;
        for (int i = 0; i < nums.length; i++) {
            int sum = 0;
            for (int j = i; j < nums.length; j++) {
                    sum += nums[j];
                    if (sum >= target) {
                        minLen = minLen > j - i + 1 ? j - i + 1 : minLen;
                }
            }
        }
        return minLen;
    }
    //输入：target = 7, nums = [2,3,1,2,4,3]

    public static int minSubArrayLen1(int target, int[] nums) {
        int minLen = Integer.MAX_VALUE;
        int k = 0;
        int sum = 0;
        int i = 0;
        while (k < nums.length  && i < nums.length) {
               sum += nums[i];
               if (sum >= target) {
                   int subLen = i - k + 1;
                   minLen = minLen > subLen ? subLen : minLen;
                   ++k;
                   i = k;
                   sum = 0;
                   continue;
               }
               i++;

        }
        return minLen;
    }