美文网首页
LeetCode 209. 长度最小的子数组

LeetCode 209. 长度最小的子数组

作者: 草莓桃子酪酪 | 来源:发表于2022-08-02 12:36 被阅读0次
    题目

    给定一个含有 n 个正整数的数组和一个正整数 target。
    找出该数组中满足其和 ≥ target 的长度最小的连续子数组 [numsl, numsl+1, ..., numsr-1, numsr] ,并返回其长度。如果不存在符合条件的子数组,返回 0。

    方法一

    分别计算每一种方式的子数组长度,最终将最小的输出。

    class Solution(object):
        def minSubArrayLen(self, target, nums):
            old = 0
            for j in range(len(nums)):
                i = j
                result = 0
                new = 0
                while result < target and i < len(nums):
                    result = result + nums[i]
                    if result < target:
                        i = i + 1
                    else:
                        new = i - j + 1
                if old == 0 or old > new and new != 0:
                    old = new
            return old
    

    会显示超出时间限制

    方法二:滑动窗口
    • 设置 start 和 end 来存放起始位置和终止位置的下标,total 来存放起始位置到终止位置的元素和,ans 来存放最小子数组的长度。
    • 首先,end 不断增加直至 total >= target,记录 ans。
    • 之后,start 右移,使得 total < target,end右移直至 total >= target,判断此次子数组的长度与之前子数组长度的大小,存储小的那个。
    • 不断循环,直至最末端。
    class Solution(object):
        def minSubArrayLen(self, target, nums):
            start = end = 0
            total = 0
            ans = len(nums) + 1
            while end < len(nums):
                total = total + nums[end]
                while total >= target:
                    ans = min(ans, end - start + 1)
                    total = total - nums[start]
                    start = start + 1
                end = end + 1
            if ans == len(nums) + 1:
                return 0
            else:
                return ans
    

    相关文章

      网友评论

          本文标题:LeetCode 209. 长度最小的子数组

          本文链接:https://www.haomeiwen.com/subject/hlhmprtx.html