【LeeCode 中等 数组 python3】209. 长度最小的子数组

想要看更加舒服的排版、更加准时的推送
关注公众号“不太灵光的程序员”
每日八点有干货推送，微信随时解答你的疑问

209. 长度最小的子数组 python3

中等 数组

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

示例：

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

进阶：

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

from typing import List


# 6%
# 执行用时：2128 ms
# 内存消耗：15.3 MB
class Solution:
    def minSubArrayLen(self, s: int, nums: List[int]) -> int:
        if not nums: return 0
        n = len(nums)
        i = 0
        j = 1
        min_len = n+1
        while i < n and j < n + 1:
            if sum(nums[i:j]) >= s:
                if min_len > j - i:
                    min_len = j - i
                i += 1
            else:
                j += 1
        if min_len > n:
            return 0
        return min_len


# 执行用时： 44 ms, 在所有 Python3 提交中击败了 97.38% 的用户
# 内存消耗： 15.3 MB, 在所有 Python3 提交中击败了 72.22% 的用户
class Solution:
    def minSubArrayLen(self, s: int, nums: List[int]) -> int:
        i = j = 0
        total = 0
        n = len(nums)
        min_len = n + 1

        while j < n:
            total += nums[j]
            j += 1
            while total >= s:
                if min_len > j - i:
                    min_len = j - i
                total -= nums[i]
                i += 1
        return 0 if min_len == n + 1 else min_len


sq = Solution()
s = 7
nums = [2, 3, 1, 2, 4, 3]
ret = sq.minSubArrayLen(s, nums)
print(ret)
s = 4
nums = [2, 3, 1, 2, 4, 3]
ret = sq.minSubArrayLen(s, nums)
print(ret)
s = 4
nums = [2]
ret = sq.minSubArrayLen(s, nums)
print(ret)

本文地址：https://blog.csdn.net/qq_23934063/article/details/107581063