【LeetCode】209. 长度最小的子数组

题目

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

思路

1. 暴力法

枚举nums中每个数num，索引为i。再枚举索引[i, len(nums)]满足条件的最小长度。
两层循环，最大时间复杂度

2. 前缀和 + 二分查找

因为数组中所有元素都是整数，所以前缀和一定是递增的。

sums = [0]
        for i in range(n):
            sums.append(sums[-1] + nums[i])

二分查找用于查找到当前索引的
重点：sums(bound) - sum(i - 1) >= s

最大时间复杂度：O(nlogn)

3. 双指针法

其实就是滑动窗口法。
时间复杂度：O(n)O(n)，其中 nn 是数组的长度。指针 left 和 right 最多各移动 nn 次。

代码

滑动窗口

class Solution:
    def minSubArrayLen(self, s: int, nums: List[int]) -> int:
        # 滑动窗口
        def isBiggerNum(nums, num):
            return sum(nums) >= num
        left, right = 0, 0
        min_len = float('INF')
        while right <= len(nums):
            right += 1
            while isBiggerNum(nums[left:right], s):
                # print(left, right)
                min_len = min(min_len, right - left)
                left += 1
        return min_len if min_len != float('INF') else 0

前缀和+二分查找

class Solution:
    def minSubArrayLen(self, s: int, nums: List[int]) -> int:
        if not nums:
            return 0
        n = len(nums)
        ans = n + 1
        sums = [0]
        for i in range(n):
            sums.append(sums[-1] + nums[i])
        for i in range(1, n + 1):
            target = s + sums[i - 1]
            bound = bisect.bisect_left(sums, target)
            if bound != len(sums):
                ans = min(ans, bound - (i - 1))
        return 0 if ans == n + 1 else ans

官方写的代码，比我要优化很多，在于保存前面已经加过的值

class Solution:
    def minSubArrayLen(self, s: int, nums: List[int]) -> int:
        if not nums:
            return 0
        n = len(nums)
        ans = n + 1
        start, end = 0, 0
        total = 0
        while end < n:
            total += nums[end]
            while total >= s:
                ans = min(ans, end - start + 1)
                total -= nums[start]
                start += 1
            end += 1
        return 0 if ans == n + 1 else ans
作者：LeetCode-Solution
链接：https://leetcode-cn.com/problems/minimum-size-subarray-sum/solution/chang-du-zui-xiao-de-zi-shu-zu-by-leetcode-solutio/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

暴力法

class Solution:
    def minSubArrayLen(self, s: int, nums: List[int]) -> int:
        if not nums:
            return 0
        n = len(nums)
        ans = n + 1
        for i in range(n):
            total = 0
            for j in range(i, n):
                total += nums[j]
                if total >= s:
                    ans = min(ans, j - i + 1)
                    break
        return 0 if ans == n + 1 else ans
作者：LeetCode-Solution
链接：https://leetcode-cn.com/problems/minimum-size-subarray-sum/solution/chang-du-zui-xiao-de-zi-shu-zu-by-leetcode-solutio/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。