209 长度最小的子数组

本文最后更新于：2022年8月26日 晚上

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

示例：

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

进阶：

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

Solution

  • 暴力解法，超时
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
// @lc code=start
class Solution {
public:
    int minSubArrayLen(int s, vector<int>& nums) {
        int res = nums.size()+1;
        for(int l=0; l<nums.size(); ++l){
            for(int r=l; r<nums.size(); ++r){
                int sum = 0;
                for(int i=l; i<=r; ++i){
                    sum += nums[i];
                }
                if(sum>=s)
                    res = min(res, r-l+1);
            }
        }
        if(res==nums.size()+1)
            return 0;
        return res;
    }
};
// @lc code=end
  • 暴力法优化，储存前缀和，超时
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
    int minSubArrayLen(int s, vector<int>& nums) {
        int res = nums.size()+1;
        // 存储前缀和
        vector<int> sums(nums.size()+1, 0);
        for(int i=1; i<=nums.size(); ++i)
            sums[i] = sums[i-1]+nums[i-1];
        
        for(int l=0; l<nums.size(); ++l){
            for(int r=l; r<nums.size(); ++r){
                if(sums[r+1]-sums[l] >= s)
                    res = min(res, r-l+1);
            }
        }
        if(res==nums.size()+1)
            return 0;
        return res;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    int minSubArrayLen(int s, vector<int>& nums) {
        int res = nums.size()+1;

        int l=0, r=0;
        int sum=0;
        for(; r<nums.size(); ++r){
            sum += nums[r];
            while(sum >= s){
                res = min(res, r-l+1);
                sum -= nums[l++];
            }
        }        
        return res==nums.size()+1 ? 0 : res;
    }
};

  • 二分搜索法，参考 liuyubobobo

  • 对于每一个 l , 可以使用二分搜索法搜索 r

  • 时间复杂度: O(nlogn)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:
    int minSubArrayLen(int s, vector<int>& nums) {
        int res = nums.size()+1;
        
        // 存储前缀和
        vector<int> sums(nums.size()+1, 0);
        for(int i=1; i<=nums.size(); ++i)
            sums[i] = sums[i-1]+nums[i-1];
        for(int l=0; l<nums.size(); ++l){
            auto r_bound = lower_bound(sums.begin(), sums.end(), sums[l]+s);
            if (r_bound != sums.end()){
                int r = r_bound-sums.begin();
                res = min(res, r-l);
            }            
        }

        if(res==nums.size()+1)
            return 0;
        return res;
    }
};

java

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
    public int minSubArrayLen(int target, int[] nums) {
        int result = nums.length + 1;
        int left = 0;
        int sum = 0;
        for (int right = 0; right < nums.length; ++right) {
            sum += nums[right];
            while (sum >= target) {
                result = Math.min(result, right - left + 1);
                sum -= nums[left++];
            }
        }
        return result == nums.length + 1 ? 0 : result;
    }
}
algo leetcode 算法

本博客所有文章除特别声明外，均采用 CC BY-SA 4.0 协议 ，转载请注明出处！