滑动窗口之长度最小的子数组

桃扇骨 2023-09-30 22:01 8阅读 0赞

[209. 长度最小的子数组][209.]

难度中等1246收藏分享切换为英文接收动态反馈

给定一个含有 `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

题解：

`start、end` 两个指针同向移动，\[start: end\] 窗口中的元素和是否大于 `target`，若大于则缩小窗口范围 （`start` 向前移动）循环判断是否大于等于 `target`

class Solution:
        def minSubArrayLen(self, target: int, nums: List[int]) -> int:
            n = len(nums)
            start, end = 0, 0
            res = n + 1
    
            total = 0
            while end < n:
                total += nums[end]
                while total >= target:
                    res = min(res, end - start + 1)
                    total -= nums[start]
                    start += 1 
                end += 1	# 窗口右边指针向后移动
    
            return 0 if res == n + 1 else res

> 参考：[长度最小的子数组][Link 1]

[209.]: https://leetcode.cn/problems/minimum-size-subarray-sum/
[Link 1]: https://leetcode.cn/problems/minimum-size-subarray-sum/solution/chang-du-zui-xiao-de-zi-shu-zu-by-leetcode-solutio/