Solutions CS101

Appearance

209.长度最小的子数组 ​

前缀和,滑动窗口, https://leetcode.cn/problems/minimum-size-subarray-sum/

给定一个含有 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 <= 10^9
  • 1 <= nums.length <= 10^5
  • 1 <= nums[i] <= 10^4
python
from typing import List, Tuple


class Solution:
    def minSubArrayLen(self, target: int, nums: List[int]) -> int:
        n = len(nums)
        slow = 0
        ans = float('inf')
        current_sum = 0
        for fast in range(n):
            current_sum += nums[fast]

            while current_sum >= target:
                ans = min(ans, fast - slow + 1)
                current_sum -= nums[slow]
                slow += 1

        return ans if ans != float('inf') else 0

if __name__ == "__main__":
    sol = Solution()
    #print(sol.minSubArrayLen(15, [1,2,3,4,5]))  # 5
    print(sol.minSubArrayLen(5, [2,3,1,1,1,1,1]))  # 2