209.长度最小的子数组

难度：中等

给定一个含有 n 个正整数的数组和一个正整数 target 。

找出该数组中满足其和 ≥ target 的长度最小的 连续子数组 [numsl, numsl+1, ..., numsr-1, numsr] ，并返回其长度。如果不存在符合条件的子数组，返回 0 。

示例 1：

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

示例 2：

输入：target = 4, nums = [1,4,4]
输出：1

示例 3：

输入：target = 11, nums = [1,1,1,1,1,1,1,1]
输出：0

提示：

1 <= target <= 10^(9)
1 <= nums.length <= 10^(5)
1 <= nums[i] <= 10^(5)

进阶：

如果你已经实现 O(n) 时间复杂度的解法，请尝试设计一个 O(n log(n)) 时间复杂度的解法。

解题思路

根据第 3 题滑动窗口的思想，这个题我考虑使用滑动窗口的方法来做。

可以直接套滑动窗口的模板。

我的思路：

设定两个指针 left 和 right，其中 right 负责寻找当前 满足其和 ≥ target 的长度最小的连续子数组 的末尾，left 指向当前当前目标子数组的开头
设定最短字串长度 minLength，初始为 Integer.MAX_VALUE
设定一个变量 sum 当作窗口，用来存储从 left 开始，到 right 结束的子数组的和
起始的时候 left 指向 0，right 往右边扫描
right 扫描到一个数字 x 的时候，增大窗口，并且更新窗口内数据 sum += x
判断 sum >= target 是否成立，若成立，则左侧窗口要收缩，同时更新 minLength 的值
right == nums.length 的时候，退出循环，返回 minLength < Integer.MAX_VALUE ? minLength : 0;

我的代码

java

public int minSubArrayLen(int target, int[] nums) {
    int left = 0;
    int right = 0;
    int sum = 0;
    int minLength = Integer.MAX_VALUE;// 记录结果
    while (right < nums.length) {
        // x 是将移入窗口的数字
        int x = nums[right];
        // 增大窗口
        right++;
        // 进行窗口内数据的一系列更新
        sum += x;
        // 判断左侧窗口是否要收缩
        while (sum >= target) {
            // d 是将移出窗口的数字
            int d = nums[left];
            // 在这里更新答案
            minLength = Math.min(minLength, right - left);
            // 缩小窗口
            left++;
            // 进行窗口内数据的一系列更新
            sum -= d;
        }
    }
    return minLength < Integer.MAX_VALUE ? minLength : 0;
}

时间复杂度：O(n)

空间复杂度：O(1)

注意：不要以为 for 里放一个 while，时间复杂度就是 O(n^2) 了。主要看每一个元素被操作的次数，每个元素在滑动窗后进来操作一次，出去操作一次，每个元素都是被操作两次，所以时间复杂度是 2 × n 也就是 O(n)。

另一种解法：前缀和 + 二分查找

思路来源（1）

如果没有想到滑动窗口的做法，那我们最容易想到的暴力做法是怎样的呢？

暴力枚举思路：

使用双层循环，外层循环 i 从数组头扫到数组尾，内层循环 j 从 i 扫到数组尾
记录从 i 到 j 的元素和，若和小于 target，则 j 持续右移，直到 j 退出循环或者和第一次大于 target
每当和第一次大于 target 的时候，记录一下此时 i 到 j 的长度，并更新 minLength
当 i 和 j 都到达数组尾的时候，返回 minLength，其中记录的就是目标值

这种做法是最容易想到和最容易实现的，但是其时间复杂度为 O(n^2)，是一种性能不高的算法。

由于我们这里频繁涉及到 区间和 的计算，而且在计算从 i 到 j 的元素和的时候，有很多重复运算，比如 1、2、3、4 ，以 1 为下标时计算了 1 + 2 + 3 + 4，以 2 为下标时计算了 2 + 3 + 4，像这种避免区间和重复计算的优化方法，我们想到了前缀和，可以在 O(1) 时间迅速得到任意区间的和问题。

前缀和

定义

对于一个给定的数列 A，它的 前缀和数列 S 中 S[i] 表示从第 0 个元素到第 i 个元素的总和。用公式表示为： $$ S[i] = \sum_{j=1}^iA[j] $$

构建方法

前缀和数列可以通过递推的方式从原数列中直接求出： $$ S[i] = S[i - 1] + A[i] $$

使用场景

前缀和的主要用处：求任意区间的元素和。

需求：有 m 个查询，需要返回从数组 A（数组长度假设为 n ）第 l 个元素到第 r 个元素的和。

【暴力做法】：遍历求和，一次查询的时间复杂度是 O(n)，那么 m 个查询的时间复杂度则是 O(mn)。

【前缀和做法】：

遍历一次数组 A，构建前缀和数组 S，时间复杂度为 O(n)
每次查询，由于区间 i 到 j 的数组 A 元素和为 S[j] - S[i-1]，所以查询的时间复杂度为 O(1)

显然采用前缀和做法后，总的时间复杂度为 O(n)，比暴力做法要好一些。

思路来源（2）

引入前缀和的概念之后，问题从 求 i 到 j 的元素和 >= target 转化为了 求 S[j] - S[i-1] >= target，但这种做法的时间复杂度呢？

构建前缀和数组的时间复杂度为 O(n)，外层循环 i 遍历原数组，时间复杂度为O(n)，内层循环遍历前缀和数组，时间复杂度为O(n)，那么整体的时间复杂度为O(n^2+n) = O(n^2)，似乎并没有什么改进？

问题出在我们内层循环寻找目标元素 j 的过程上，注意到 这道题保证了数组中每个元素都为正，所以前缀和数组一定是递增的、有序的。

那么这种在有序数组中进行线性查找的问题，我们未必要采用死板的从头遍历，而是可以引入二分查找，来快速找到第一个满足 S[j] - S[i-1] >= target 的 j。

而且二分查找的时间复杂度为 O(log n)，那么整个算法的时间复杂度应该为 O(n + nlog n) = O(nlog n)。

注意这里的二分查找在基础的版本上，需要改造一下：

当元素存在时返回其下标
当元素不存在时，返回其第一个理论插入点的下标+1后的相反数

代码实现

java

public int minSubArrayLen(int target, int[] nums) {
    if (nums.length == 0) {
        return 0;
    }
    /**
     * 构建前缀和数组
     * 为了方便计算，令 length = n + 1
     * S[0] = 0 意味着前 0 个元素的前缀和为 0
     * S[1] = A[0] 前 1 个元素的前缀和为 A[0]
     * 以此类推
     */
    int[] prefixSum = getPrefixSumArray(nums);
    // 记录最小值
    int minLength = Integer.MAX_VALUE;
    for (int i = 1; i <= nums.length; i++) {
        int bound = binarySearch(prefixSum, i, nums.length, target + prefixSum[i - 1]);
        if (bound < 0) {
            bound = -bound - 1;
        }
        if (bound <= nums.length) {
            minLength = Math.min(minLength, bound - (i - 1));
        }
    }
    return minLength == Integer.MAX_VALUE ? 0 : minLength;
}

// 构建前缀和数组
private int[] getPrefixSumArray(int[] nums) {
    int[] prefixSum  = new int[nums.length + 1];
    prefixSum[0] = 0;
    for (int i = 1; i <= nums.length; i++) {
        prefixSum[i] = prefixSum[i - 1] + nums[i - 1];
    }
    return prefixSum;
}

// 改造后的二分查找
private int binarySearch(int[] prefixSum, int left, int right, int key) {
    while (left <= right) {
        int mid = left + (right - left) / 2; // 避免数值溢出
        if (prefixSum[mid] < key) {
            left = mid + 1;
        } else if (prefixSum[mid] > key) {
            right = mid - 1;
        } else {
            return mid; //发现目标值
        }
    }
    return -(left + 1);  // 目标值不存在
}

改造后的二分查找为什么返回插入点的时候，不是直接返回 -left 而是返回 -(left + 1) 呢？

当找到 key 值时，函数会返回 mid，即 key 在数组中的正确索引位置。

如果未找到 key，则 while 循环会退出，此时 low 会大于 high。在这种情况下，low 指向的位置是 key 可以插入数组以保持排序顺序的位置。

但是，仅返回 -low 是不够的，因为在索引 0 处找到 key 的情况下会返回 0，但是 0 的负数还是 0，这样会导致歧义，也就是说：我们需要一种方法来区分“未找到”和“在索引 0 处找到”的情况。

为了解决这个问题，代码返回了 -(low + 1)。通过对 low 加 1 并取反，可以确保结果是负数且大于等于 -1。因此，如果未找到 key，函数将返回一个负值，表示应该将 key 插入的位置。

简而言之，返回 -(low + 1) 的选择是二分查找算法中的一种约定，用于处理“未找到”和“在索引 0 处找到”的情况，而不会产生歧义。它允许函数在“未找到”情况下返回负值，同时仍然能够表示“找到”的正确索引位置。

总结

有同学很容易就想到了 O(n) 的解法，不理解学习O(n logn)解法的意义。

然而生活不是刷题，生活中的“最优解”往往是多种方法比较后的“择优录取”，他甚至都不是理论上的最优解。

多掌握一种解法，就多一种可能。

209.长度最小的子数组 ​

解题思路 ​

我的代码 ​

另一种解法：前缀和 + 二分查找 ​

思路来源（1） ​

前缀和 ​

定义 ​

构建方法 ​

使用场景 ​

思路来源（2） ​

代码实现 ​

总结 ​