209. Minimum Size Subarray Sum

题目描述和难度

题目描述：

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

示例:

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

进阶:

如果你已经完成了O(n) 时间复杂度的解法, 请尝试 O(n log n) 时间复杂度的解法。

题目难度：中等。
英文网址：209. Minimum Size Subarray Sum 。
中文网址：209. 长度最小的子数组。

思路分析

求解关键：思路一：使用二分查找为什么能使用二分查找？“二分查找”不是要求数组是有序的吗？
“数组是正整数”这个条件在使用二分法解决这道问题中是至关重要的。因为“数组是正整数”，所以前缀和数组一定是严格增加的。任意区间和可以通过前缀和数组得到，这是我们常见的一种做法。起点固定的时候，区间越长，区间和越大。

思路二：使用滑动窗口的技巧来完成，要看过一遍整个数组的元素，所以时间复杂度是 $O(n)$。

因为要求的是满足区间和 >= s 的最小子区间的长度，因此，我们从左向右进行扫描。

当区间和小于 s 的时候，右区间的端点向右扩展，这一点依赖外层循环的遍历就可以完成；
一旦区间和大于等于 s，尝试一步一步缩小左区间端点，看看是否能得到一个更短的区间，满足区间和 >=s，这一步通过一个内层循环实现。

参考解答

参考解答1：构造前缀和数组，使用二分查找法。

public class Solution {

    public int minSubArrayLen(int s, int[] nums) {
        int len = nums.length;
        if (len == 0) {
            return 0;
        }
        // 构造前缀和数组
        // 因为 nums 全都是正整数，因此 preSum 严格单调增加
        int[] preSum = new int[len];
        preSum[0] = nums[0];
        for (int i = 1; i < len; i++) {
            preSum[i] = preSum[i - 1] + nums[i];
        }
        // 因为前缀和数组严格单调增加，因此我们可以使用二分查找算法
        // 最后一位没有下一位了，所以外层遍历到最后一位的前一位就可以了
        int ret = len + 1;
        for (int i = 0; i < len - 1; i++) {
            // 计算区间和
            int l = i;
            int r = len - 1;
            // 设置成一个比较大的数，但是这个数有下界
            // i 的最大值是 len-2,
            // ans - i + 1 >= len + 1
            // ans >= i + len = 2 * len -2
            int ans = 2 * len - 2;
            // int ans = 2 * len - 1; 能通过
            // int ans = 2 * len - 3; 不能通过
            // 退出循环的条件是 l > r
            while (l <= r) {
                int mid = l + (r - l) / 2;
                // 计算一下区间和，找一个位置，使得这个位置到索引 i 的区间和为 s
                // 13 14 15 17 19 20
                int segmentSum = preSum[mid] - (i == 0 ? 0 : preSum[i - 1]);
                if (segmentSum >= s) {
                    ans = mid;
                    r = mid - 1;
                } else {
                    l = mid + 1;
                }
            }
            ret = Integer.min(ans - i + 1, ret);
        }
        if (ret == len + 1) {
            return 0;
        }
        return ret;
    }
}

参考解答2：使用滑动窗口

public class Solution {

    public int minSubArrayLen(int s, int[] nums) {
        int len = nums.length;
        if (len == 0) {
            return 0;
        }
        int l = 0;
        int r = -1;
        // 注意1：既然是求最小的长度，初始值应该设置成一个不可能达到的上限
        int minSubArrayLen = len + 1;
        int sum = 0;
        for (int i = 0; i < len; i++) {
            sum += nums[i];
            r++;
            // 注意2：这里的 = 号不要忘记了
            while (sum >= s) {
                minSubArrayLen = Integer.min(minSubArrayLen, r - l + 1);
                sum -= nums[l];
                l++;
            }
        }
        // 如果全部数组元素加起来都 <s ，即 minSubArrayLen 的值没有被更新，根据题意，返回 0
        if (minSubArrayLen == len + 1) {
            return 0;
        }
        return minSubArrayLen;
    }

    // 与上面的写法相同，只是边界条件设置不一样
    public int minSubArrayLen1(int s, int[] nums) {
        int len = nums.length;
        if (len == 0) {
            return 0;
        }
        int l = 0;
        int r = 0;
        int minSubArrayLen = len + 1;
        int segmentSum = 0;
        for (int num : nums) {
            segmentSum += num;
            r++;
            // 注意：根据题意"找出该数组中满足其和 ≥ s 的长度最小的子数组"
            // 注意这个边界条件
            while (segmentSum >= s) {
                minSubArrayLen = Integer.min(minSubArrayLen, r - l);
                segmentSum -= nums[l];
                l++;
            }
        }
        if (minSubArrayLen == len + 1) {
            return 0;
        }
        return minSubArrayLen;
    }

    // 3 种写法本质上都是一样：滑动窗口
    public int minSubArrayLen2(int s, int[] nums) {
        int len = nums.length;
        if (len == 0) {
            return 0;
        }
        int l = 0;
        int segmentSum = 0;
        int minSubArrayLen = len + 1;
        for (int i = 0; i < len; i++) {

            segmentSum += nums[i];
            while (segmentSum >= s) {
                minSubArrayLen = Integer.min(minSubArrayLen, i - l + 1);
                segmentSum -= nums[l];
                l++;
            }
        }
        if (minSubArrayLen == len + 1) {
            return 0;
        }
        return minSubArrayLen;
    }
}

本篇文章的地址为 https://liweiwei1419.github.io/leetcode-solution/leetcode-0209-minimum-size-subarray-sum ，如果我的题解有错误，或者您有更好的解法，欢迎您告诉我 liweiwei1419@gmail.com 。