欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

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

程序员文章站 2023-02-17 08:02:37
想要看更加舒服的排版、更加准时的推送关注公众号“不太灵光的程序员”每日八点有干货推送,微信随时解答你的疑问209. 长度最小的子数组 python3中等 数组给定一个含有 n 个正整数的数组和一个正整数 s ,找出该数组中满足其和 ≥ s 的长度最小的 连续 子数组,并返回其长度。如果不存在符合条件的子数组,返回 0。示例:输入:s = 7, nums = [2,3,1,2,4,3]输出:2解释:子数组 [4,3] 是该条件下的长度最小的子数组。进阶:如果你已经完成了 O(n) 时....

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

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