数组 - Leetcode-209：长度最小的子数组 - 《算法珠玑》

问题
解法一：暴力解法
解法二：滑动窗口
- 思路

问题

给定一个含有 n 个正整数的数组和一个正整数 s ，找出该数组中满足其和 ≥ s 的长度最小的连续子数组，并返回其长度。如果不存在符合条件的子数组，返回 0。

示例：
输入：s = 7, nums = [2,3,1,2,4,3]
输出：2
解释：子数组 [4,3] 是该条件下的长度最小的子数组。

解法一：暴力解法

package leetcode;
public class leetcode_209_1 {
    public int minSubArrayLen(int s, int[] nums) {
        int n = nums.length;
        if (n == 0) {
            return 0;
        }
        int ans = Integer.MAX_VALUE;
        for (int i = 0; i < n; i++) {
            int sum = 0;
            for (int j = i; j < n; j++) {
                sum += nums[j];
                if (sum >= s) {
                    ans = Math.min(ans, j - i + 1); //比较两个数的大小
                    break;
                }
            }
        }
        System.out.println(ans);
        return ans == Integer.MAX_VALUE ? 0 : ans;
    }
    public static void main(String[] args){
        leetcode_209_1 lt = new leetcode_209_1();
        int[] nums = new int[]{2,3,1,2,4,3};
        int ans = lt.minSubArrayLen(7, nums);
    }
}

时间复杂度：，其中 n 是数组的长度。需要遍历每个下标作为子数组的开始下标，对于每个开始下标，需要遍历其后面的下标得到长度最小的子数组
空间复杂度：O(1)

解法二：滑动窗口

滑动窗口——就是不断的调节子序列的起始位置和终止位置，从而得出我们要想的结果
窗口就是 满足其和 ≥ s 的长度最小的连续子数组
窗口的起始位置如何移动：如果当前窗口的值大于s了，窗口就要向前移动了
窗口的结束位置如何移动：窗口的结束位置就是遍历数组的指针，窗口的起始位置设置为数组的起始位置就可以
代码精髓：
```
while(n >= s){
  subLength = (j - i + 1); // 取子序列的长度
  result = result < subLength ? result : subLength;
  sum -= nums[i++]; // 这里体现出滑动窗口的精髓之处，不断变更i（子序列的起始位置）
}
```
思路
定义两个指针和分别表示子数组（滑动窗口窗口）的开始位置和结束位置，维护变量存储子数组中的元素和（即从到的元素和）；初始状态下，和都指向下标，的值为。每一轮迭代，将加到，如果，则更新子数组的最小长度（此时子数组的长度是），然后将从中减去并将右移，直到，在此过程中同样更新子数组的最小长度。在每一轮迭代的最后，将右移 ```java package leetcode;

public class leetcode_209_2 { public int minSubArrayLen(int s, int[] nums) { int n = nums.length; if (n == 0) { return 0; } int ans = Integer.MAX_VALUE; int start = 0, end = 0; int sum = 0; while (end < n) { sum += nums[end]; while (sum >= s) { ans = Math.min(ans, end - start + 1); sum -= nums[start]; start++; } end++; } return ans == Integer.MAX_VALUE ? 0 : ans; }

public static void main(String[] args){
    leetcode_209_2 lt = new leetcode_209_2();
    int nums[] = new int[]{2,3,1,2,4,3};
    int i = lt.minSubArrayLen(7, nums);
    System.out.println(i);
}

} ```

时间复杂度：O(n)，两个指针最多各移动n次
空间复杂度：O(1)

Leetcode-209：长度最小的子数组

问题

解法一：暴力解法

解法二：滑动窗口

思路