leetcode209 Minimum Size Subarray Sum-zh

# 209. 长度最小的子数组 (opens new window)

# 题目描述

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

找出该数组中满足其和≥ target的长度最小的 连续子数组 [nums_l, nums_l+1, ..., nums_r-1, nums_r] ，并返回其长度。如果不存在符合条件的子数组，返回 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⁹
1 <= nums.length <= 10⁵
1 <= nums[i] <= 10⁵

进阶：

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

# 解法

“前缀和 + 二分查找”，先求出数组的前缀和 preSum，然后根据 preSum[i] - preSum[j] >= target => preSum[i] >= preSum[j] + target，对 preSum[i] 进行二分查找，然后更新最小长度即可。时间复杂度 O(n logn)。

也可以用“滑动窗口”。

使用指针 left, right 分别表示子数组的开始位置和结束位置，维护变量 sum 表示子数组 nums[left...right] 元素之和。初始时 left, right 均指向 0。每一次迭代，将 nums[right] 加到 sum，如果此时 sum >= target，更新最小长度即可。然后将 sum 减去 nums[left]，接着 left 指针右移直至 sum < target。每一次迭代最后，将 right 指针右移。时间复杂度 O(n)。

# Python3

“前缀和 + 二分查找”。

class Solution:
    def minSubArrayLen(self, target: int, nums: List[int]) -> int:
        n = len(nums)
        pre_sum = [0] * (n + 1)
        for i in range(1, n + 1):
            pre_sum[i] = pre_sum[i - 1] + nums[i - 1]
        res = n + 1
        for i in range(1, n + 1):
            t = pre_sum[i - 1] + target
            left, right = 0, n
            while left < right:
                mid = (left + right) >> 1
                if pre_sum[mid] >= t:
                    right = mid
                else:
                    left = mid + 1
            if pre_sum[left] - pre_sum[i - 1] >= target:
                res = min(res, left - i + 1)
        return 0 if res == n + 1 else res

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

“滑动窗口”。

class Solution:
    def minSubArrayLen(self, target: int, nums: List[int]) -> int:
        n = len(nums)
        left = right = 0
        sum, res = 0, n + 1
        while right < n:
            sum += nums[right]
            while sum >= target:
                res = min(res, right - left + 1)
                sum -= nums[left]
                left += 1
            right += 1
        return 0 if res == n + 1 else res

1
2
3
4
5
6
7
8
9
10
11
12
13

# Java

“前缀和 + 二分查找”。

class Solution {
    public int minSubArrayLen(int target, int[] nums) {
        int n = nums.length;
        int[] preSum = new int[n + 1];
        for (int i = 1; i <= n; ++i) {
            preSum[i] = preSum[i - 1] +nums[i - 1];
        }
        int res = n + 1;
        for (int i = 1; i <= n; ++i) {
            int t = preSum[i - 1] + target;
            int left = 0, right = n;
            while (left < right) {
                int mid = (left + right) >> 1;
                if (preSum[mid] >= t) {
                    right = mid;
                } else {
                    left = mid + 1;
                }
            }
            if (preSum[left] - preSum[i - 1] >= target) {
                res = Math.min(res, left - i + 1);
            }
        }
        return res == n + 1 ? 0 : res;
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

“滑动窗口”。

class Solution {
    public int minSubArrayLen(int target, int[] nums) {
        int n = nums.length;
        int left = 0, right = 0;
        int sum = 0, res = n + 1;
        while (right < n) {
            sum += nums[right];
            while (sum >= target) {
                res = Math.min(res, right - left + 1);
                sum -= nums[left++];
            }
            ++right;
        }
        return res == n + 1 ? 0 : res;
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

# C#

public class Solution {
    public int MinSubArrayLen(int target, int[] nums) {
        int n = nums.Length;
        int left = 0, right = 0;
        int sum = 0, res = n + 1;
        while (right < n)
        {
            sum += nums[right];
            while (sum >= target)
            {
                res = Math.Min(res, right - left + 1);
                sum -= nums[left++];
            }
            ++right;
        }
        return res == n + 1 ? 0 : res;
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

# ...

编辑

#leetcode

上次更新: 2021/10/30, 12:58:38

← leetcode208 Implement Trie (Prefix Tree)-zh leetcode210 Course Schedule II-zh→