题目描述

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

样例

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

进阶：

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

算法1

前缀和 + 二分

• 1、计算出数字的前缀和f[]，即找到f[j] - f[i] >= s 的最小连续长度j - i
• 2、枚举i位置，固定i位置，在后面的元素中找出f[j] - f[i] >= s 最小的j位置，则对应的长度j - i就是当前位置i的最小连续长度
• 3、由于f[]数组是单调的，因此在区间[i + 1, n]找最小的f[j]，由于可能会存在[i + 1, n]区间中都不存在一个数j，使得f[j] - f[i] >= s，为了方便区分存不存在，因此左右边界开始设置为[i, n + 1]，当最后落在i或者n + 1时，则表示不存在f[j]这个数

时间复杂度 $O(nlogn)$

Java 代码

class Solution {
    public int minSubArrayLen(int s, int[] nums) {
        int n = nums.length;
        int[] f = new int[n + 1];
        for(int i = 1;i <= n;i ++) f[i] = f[i - 1] + nums[i - 1];

        int ans = 0x3f3f3f3f;
        for(int i = 0;i < n;i ++)
        {
            int l = i, r = n + 1;
            while(l < r)
            {
                int mid = l + r >> 1;
                if(f[mid] - f[i] >= s) r = mid;
                else l = mid + 1;
            }
            if(r >= i + 1 && r <= n) ans = Math.min(ans, r - i);
        }
        if(ans == 0x3f3f3f3f) return 0;
        return ans;
    }
}

算法2

前缀和 + 双指针

• 1、计算出数字的前缀和f[]，即找到f[j] - f[i] >= s 的最小连续长度i - j
• 2、用双指针i和j维护[i + 1,j]区间内总和 < s，每次j往前走时，i始终要维护上述状态，每次存在f[j] - f[i] >= s,都更新ans

时间复杂度 $O(n)$

Java 代码

class Solution {
    public int minSubArrayLen(int s, int[] nums) {
        int n = nums.length;
        int[] f = new int[n + 1];
        for(int i = 1;i <= n;i ++) f[i] = f[i - 1] + nums[i - 1];

        int ans = 0x3f3f3f3f;
        for(int j = 1, i = 0;j <= n;j ++)
        {
            while(f[j] - f[i] >= s) 
            {
                ans = Math.min(ans, j - i);
                i ++;
            }
        }
        if(ans == 0x3f3f3f3f) return 0;
        return ans;
    }
}