剑指 Offer II 008. 和大于等于 target 的最短子数组

题目链接

剑指 Offer II 008. 和大于等于 target 的最短子数组 mid

题目描述

给定一个含有 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$

解法一前缀和 + 二分

如果我们要快速求一段连续区间的和可以使用前缀和数组 ss[i]代表 nums[1],nums[2],nums[3]...nums[i]的和,那么如果我们要求区间 [L,R]的和即 s[R] - s[L-1]。

因为给定数据都是大于1的所以 nums的前缀和数组 s必然是单调递增的。

所以我们就可以使用 二分 的方式快速求以 nums[i]为左边界以nums[R]R是我们要求的为右边界且区间 [i,R]的和大于等于 target。

对于 i$(1<=i<=n)$我们都可以用这样的方式求在这个过程中我们不断的更新最小区间的长度。

时间复杂度$O(nlogn)$

C++代码

class Solution {
public:
    int minSubArrayLen(int target, vector<int>& nums) {
        int n = nums.size();
        vector<int> s(n+1);
        //构建前缀和数组
        for(int i = 1;i <= n;i++) s[i] = s[i-1] + nums[i-1];

        int len = 1e5;

        for(int i = 1;i <= n;i++){
            int l = i,r = n;
            //二分 求第一个 s[r] - s[i-1] >= target 的下标r
            while(l<r){
                int mid = (l + r) >> 1;
                if(s[mid] - s[i-1] >= target) r = mid;
                else l = mid + 1;
            }
            //更新答案
            if(s[r] - s[i-1] >= target) len = min(len,l - i + 1);
        }

        return len == 1e5 ? 0 : len;
    }
};

Java代码

class Solution {
    public int minSubArrayLen(int target, int[] nums) {
        int n = nums.length;
        int[] s = new int[n+1];

        for(int i = 1;i <= n;i++) s[i] = s[i-1] + nums[i-1];

        int len = 100000;

        for(int i = 1;i <= n;i++){
            int l = i,r = n;
            while(l<r){
                int mid = (l + r) >> 1;
                if(s[mid] - s[i-1] >= target) r = mid;
                else l = mid + 1;
            }
            if(s[r] - s[i-1] >= target) len = Math.min(len,l - i + 1);
        }

        return len == 100000 ? 0 : len;
    }
}

解法二滑动窗口

我们可以使用两个指针 i和j维护一个刚好 大于等于 target的区间维护区间的同时不断更新答案即可。

时间复杂度$O(n)$

C++代码

class Solution {
public:
    int minSubArrayLen(int target, vector<int>& nums) {
        int len = 1e9;
        int n = nums.size();
        for(int sum = 0,i = 0,j = 0;j < n;j++){
            sum += nums[j];
            //缩短区间
            while(sum - nums[i] >= target){
                sum -= nums[i];
                i++;
            }
            //更新答案
            if(sum >= target) len = min(len,j - i + 1);
        }
        return len == 1e9 ? 0 : len;
    }
};

Java代码

class Solution {
    public int minSubArrayLen(int target, int[] nums) {
        int n = nums.length;
        int len = 100000;
        for(int sum = 0,i = 0,j = 0;j < n;j++){
            sum += nums[j];
            while(sum - nums[i] >= target){
                sum -= nums[i++];
            }
            if(sum >= target) len = Math.min(len,j-i+1);
        }
        return len == 100000 ? 0 : len;
    }
}