华为 OD 训练营 · 题解精讲

LC209. 长度最小的子数组

LC209. 长度最小的子数组视频地址：https://uha.xet.tech/s/2OIwSS

题目描述

给定一个含有 n 个正整数的数组和一个正整数 target 。找出该数组中满足其和 ≥ target 的长度最小的连续子数组 [numsl, numsl+1, ..., numsr-1, numsr] ，并返回其长度。如果不存在符合条件的子数组，返回 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 <= 109 1 <= nums.length <= 105 1 <= nums[i] <= 105 进阶：如果你已经实现 O(n) 时间复杂度的解法, 请尝试设计一个 O(n log(n)) 时间复杂度的解法。

题目解析

很经典的滑动窗口的题目。具体操作如下： 1、初始化一个滑动窗口，左边界位置为 0，接下来开始设置右边界的位置，通过数组不断的去调整右边界的位置，所以一开始右边界的位置也是 0，如果数组为空，那么这个窗口就不存在；如果数组不为空，那么窗口就是第一个元素。 Pnk1bpWYCoT71cxBYuRc4x9Vnge.png

2、计算此时滑动窗口里面所有元素的值。 3、如果滑动窗口的元素和小于了 target，那么说明还没有找到了一个满足条件的连续子数组，需要继续扩充滑动窗口，扩充的方式就是让右边界向右移动。 AMrpbZ5R3oyKUmx8PvPcoky2nZh.png

4、如果滑动窗口的元素和大于等于了 target，那么说明找到了一个满足条件的连续子数组，计算出这个连续子数组的长度来，把这个结果 result 和之前的保存的结果进行对比取最小值。 Wd0IbxVjSo3lJdxMHKCcFf3DnJw.png

5、基于 4 的情况，需要开始尝试缩小滑动窗口，去寻找更短的滑动窗口，缩小的方法就是不断的移动左边界，直到滑动窗口里面的元素和小于了 target 为止，在移动过程中，如果发现滑动窗口的元素和依旧大于等于了 target，继续缩小同时更新 result。 PwNBbdtFyohEoOxDeSKcem6RnUb.png

6、最后需要注意一点，一开始，result 可以初始化为一个超过数组长度的值，这样的目的是为了最后返回结果的时候判断 result 有没有被更新，如果没有被更新，并且滑动窗口的长度不可能为 result，因为超过了数组的长度，那就代表不存在符合条件的子数组，需要返回 0 ，比如 target = 11， nums = [1,1,1,1,1,1,1,1]，先设置 result = 9，执行完后续代码，result 依旧为 9，代表 nums 里面找不到一个子数组和大于等于 11 ，需要返回 0。

参考代码

class Solution:
    def minSubArrayLen(self, target: int, nums: List[int]) -> int:
        # 滑动窗口的左端
        left = 0

        # 滑动窗口中所有元素的和
        sum = 0

        # 记录滑动窗口的长度，并且不断更新获取最小的那个
        # 一开始，result 可以初始化为一个超过数组长度的值
        # 这样的目的是为了最后返回结果的时候判断 result 有没有被更新
        # 如果没有被更新，并且滑动窗口的长度不可能为 result，因为超过了数组的长度
        # 那就代表不存在符合条件的子数组，需要返回 0 
        # 比如 target = 11, nums = [1,1,1,1,1,1,1,1]
        # 先设置 result = 9，执行完后续代码，result 依旧为 9
        # 代表 nums 里面找不到一个子数组和大于等于 11 ，需要返回 0
        result = len(nums) + 1
        
        # 滑动窗口的右端从 0 开始，这样，当 nums 为空时，可以直接跳出 for 循环
        for right in range(len(nums)) :

            # 滑动窗口中加入了 nums[right] 这个元素
            # 滑动窗口元素和需要发生变化
            sum += nums[right]

            # 变化之后需要判断一下，如果滑动窗口的元素和大于等于了 target
            # 那么这个时候就需要不断的向右移动 left，缩小滑动窗口的长度
            while sum >= target : 
                
                # 在获取到一个满足要求的子数组时，更新 result 的值
                result = min(result, right - left + 1)

                # 把 nums[left] 移除滑动窗口
                sum -= nums[left]

                # 即 left 向右移动
                left += 1

      
        # 返回结果
        return 0 if result == len(nums) + 1 else result
四、复杂度分析
时间复杂度：O(n)，其中 n 是数组的长度。
空间复杂度：O(1)。

← 上一篇

LC207. 课程表

LC210. 课程表II