跳至主要內容

0209. 长度最小的子数组

ITCharge大约 2 分钟

0209. 长度最小的子数组open in new window

  • 标签:数组、二分查找、前缀和、滑动窗口
  • 难度:中等

题目大意

描述:给定一个只包含正整数的数组 numsnums 和一个正整数 targettarget

要求:找出数组中满足和大于等于 targettarget 的长度最小的「连续子数组」,并返回其长度。如果不存在符合条件的子数组,返回 00

说明

  • 1target1091 \le target \le 10^9
  • 1nums.length1051 \le nums.length \le 10^5
  • 1nums[i]1051 \le nums[i] \le 10^5

示例

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

解题思路

思路 1:滑动窗口(不定长度)

最直接的做法是暴力枚举,时间复杂度为 O(n2)O(n^2)。但是我们可以利用滑动窗口的方法,在时间复杂度为 O(n)O(n) 的范围内解决问题。

用滑动窗口来记录连续子数组的和,设定两个指针:leftleftrightright,分别指向滑动窗口的左右边界,保证窗口中的和刚好大于等于 targettarget

  1. 一开始,leftleftrightright 都指向 00
  2. 向右移动 rightright,将最右侧元素加入当前窗口和 windowsumwindow\underline{}sum 中。
  3. 如果 windowsumtargetwindow\underline{}sum \ge target,则不断右移 leftleft,缩小滑动窗口长度,并更新窗口和的最小值,直到 windowsum<targetwindow\underline{}sum < target
  4. 然后继续右移 rightright,直到 rightlen(nums)right \ge len(nums) 结束。
  5. 输出窗口和的最小值作为答案。

思路 1:代码

class Solution:
    def minSubArrayLen(self, target: int, nums: List[int]) -> int:
        size = len(nums)
        ans = size + 1
        left = 0
        right = 0
        window_sum = 0

        while right < size:
            window_sum += nums[right]

            while window_sum >= target:
                ans = min(ans, right - left + 1)
                window_sum -= nums[left]
                left += 1

            right += 1

        return ans if ans != size + 1 else 0

思路 1:复杂度分析

  • 时间复杂度O(n)O(n)
  • 空间复杂度O(1)O(1)