[209][中等][滑动数组] 长度最小的子数组

题目描述

209. 长度最小的子数组

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

示例:

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

进阶:

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

解题思路

解题思路: 长度最小的子数组

双指针

数组中连续子序列的问题一种常见的思路就是滑动窗口, 即双指针.

定义两个指针start和end, 分别指向子数组开始和结束的地方, 初始都为0. 将它们之间子数组中数字之和记为sum, 如果$\text{sum} \ge s$, 需要更新起始指针start, 直到对应的$\text{sum} \lt s$.

然后逐步移动end指针, 直到又出现$\text{sum} \ge s$, 然后重复上述步骤.

在这个过程中, 在每次$\text{sum} \ge s$时, 都比较子数组长度, 并记录最短子数组.

class Solution:
    def minSubArrayLen(self, s: int, nums: List[int]) -> int:
        n = len(nums)
        if n == 0:
            return 0

        start, end = 0, 0
        current, length = 0, n + 1
        while end < n:
            current += nums[end]
            while current >= s:
                length = min(length, end - start + 1)
                current -= nums[start]
                start += 1
            end += 1
        return 0 if length > n else length

前缀和

数组中连续子序列的问题另一种常见的思路前缀和.

要求:

• 数组中每个元素都为正, 前缀和序列一定是递增的, 这样查找的结果才是唯一的

创建一个数组$\text{sums}$来存储数组的前缀和, 即$\text{sums}[i]$表示从$\text{num}[0]$到$\text{num}[i-1]$之和.

对于下标$i$, 我们找到$\text{sums}[i] + s$在$\text{sums}$中的位置$\text{bound}$, 这样从$i$开始到$\text{bound}-1$位置$\text{num}$中所有数之和为$s$, 对应的子序列长度为$\text{bound}-i$.

边界条件为$\text{bound}-1$必须小于$\text{sums}$的长度, 即小于$\text{len}(\text{num})+1$, 这样才能在$\text{sums}$中去到值.

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])  # `sums`最终的长度为`n+1`

        for i in range(n):
            target = s + sums[i]
            bound = bisect.bisect_left(sums, target)
            if bound != len(sums):
                ans = min(ans, bound - i)

        return 0 if ans == n + 1 else ans