【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
上一篇: day02_进制&python入门
下一篇: python中xrange用法分析