首页 > 编程语言 >LeetCode 209 Minimum Size Subarray Sum 题目解析和python代码

LeetCode 209 Minimum Size Subarray Sum 题目解析和python代码

时间:2024-10-08 15:20:39浏览次数:10  
标签:end target start 209 Sum nums len python min

题目
Given an array of positive integers nums and a positive integer target, return the minimal length of a
subarray
whose sum is greater than or equal to target. If there is no such subarray, return 0 instead.

Example 1:

Input: target = 7, nums = [2,3,1,2,4,3]
Output: 2
Explanation: The subarray [4,3] has the minimal length under the problem constraint.
Example 2:

Input: target = 4, nums = [1,4,4]
Output: 1
Example 3:

Input: target = 11, nums = [1,1,1,1,1,1,1,1]
Output: 0

Constraints:

1 <= target <= 109
1 <= nums.length <= 105
1 <= nums[i] <= 104

Follow up: If you have figured out the O(n) solution, try coding another solution of which the time complexity is O(n log(n)).

题目解析
这里我们可以使用 sliding window 的技巧。
我们可以使用两个 pointers,一个是 start 一个是 end,两个指针都从array的开头开始。
向右移动 end 指针来提高 window 的大小,每一次移动指针都把 nums[end] 添加到现在的和。
当这个和大于或等于 target 时,我们要开始缩短 subarray 的长度。于是我们开始移动 start 这个指针来缩小 window 的大小。通过不停的向右移动 start 指针,直到找到最短的 subarray 的长度。

class Solution:
    def minSubArrayLen(self, target: int, nums: List[int]) -> int:
        start = 0
        curr_sum = 0
        min_len = float('inf')

        for end in range(len(nums)):
            curr_sum += nums[end]

            while curr_sum >= target:
                min_len = min(min_len, end - start + 1)
                curr_sum -= nums[start]
                start += 1
            
        return min_len if min_len != float('inf') else 0

Time complexity 是 O(n)。
Space complexity 是 O(1)。

标签:end,target,start,209,Sum,nums,len,python,min
From: https://blog.csdn.net/weixin_57266891/article/details/142737988

相关文章

  • 【Python Matplotlib 教程】第23课时-Matplotlib 等高线图
    Matplotlib等高线图等高线图(有时称为水平面图)是一种将三维表面绘制在二维平面上的方法。它在y轴上绘制了两个预测变量X和Y,而响应变量Z则以等高线的形式呈现。这些等高线有时被称为z-切片或等响应值。如果您想观察变量Z随着两个输入变量X和Y的变化情况,使得Z=f(X,Y),则等高线图......
  • 基于Python+Scrapy的高校岗位招聘和分析平台(源码+vue+hadoop+hive+部署文档+可视化大
    收藏关注不迷路!!......
  • python基于深度学习的短视频内容理解与推荐系统(源码+vue+hadoop+hive+部署文档+可视
    收藏关注不迷路!!......
  • Python精选200Tips:186-190
    针对序列(时间、文本)数据的网络结构续P186--双向LSTM(BidirectionalLongShort-TermMemory2005)(1)模型结构说明(2)创新性说明(3)示例代码:IMDB电影评论情感分析P187--变换器结构(Transformer2017)(1)模型结构说明(2)创新性说明(3)示例代码:模拟气象数据预测(多输出多输出)P188--......
  • 彻底搞懂【Python】切片操作
    在利用Python解决各种实际问题的过程中,经常会遇到从某个对象中抽取部分值的情况,切片操作正是专门用于完成这一操作的有力武器。理论上而言,只要条件表达式得当,可以通过单次或多次切片操作实现任意切取目标值。切片操作的基本语法比较简单,但如果不彻底搞清楚内在逻辑,也极容易产生......
  • Python 格式化输出的高级技巧与应用
    在Python中,格式化输出是一种非常有用的技术,它可以让我们以更清晰、更易读的方式展示数据。以下是一些关于Python格式化输出的高级技巧和代码示例: 使用占位符进行格式化name = "Alice"age = 25print("My name is %s and I am %d years old." % (name, ......
  • Python 代理模式:控制对象访问的智能中介
    在Python编程中,代理模式(ProxyPattern)是一种非常有用的设计模式,它在许多场景下能够为我们提供更加灵活和可控的对象访问方式。代理模式就像是一个中间人,它站在客户端和真实对象之间,代替真实对象处理请求,并且可以在这个过程中添加额外的逻辑,如权限验证、懒加载等。本文将深......
  • Python 享元模式:高效利用内存的设计模式
    在Python编程中,随着程序规模的增大和数据量的增加,内存管理变得至关重要。享元模式(FlyweightPattern)作为一种结构型设计模式,为我们提供了一种在某些场景下有效管理内存、提高系统性能的方法。本文将深入探讨Python中的享元模式,包括其概念、关键要点、实现方式、应用场景......
  • Python 外观模式:简化复杂系统交互的设计模式
    在软件开发过程中,随着系统规模的不断扩大和功能的日益复杂,子系统之间的交互可能变得错综复杂。Python中的外观模式(FacadePattern)提供了一种有效的解决方案,它能够简化这些复杂的交互,为客户端提供一个统一、易用的接口来访问系统。本文将深入探讨Python中的外观模式,详细阐......
  • Python 装饰器模式:增强函数与类的优雅之道
    在Python编程中,装饰器模式(DecoratorPattern)是一种强大且灵活的设计模式,它允许我们在不修改现有函数或类的结构的情况下,动态地添加额外的功能。这种模式遵循了开放-封闭原则,即软件实体(类、模块、函数等)应该对扩展开放,对修改封闭。本文将深入探讨Python中的装饰器模式,......