【leetcode-Python】-滑动窗口-209. Minimum Size Subarray Sum

题目链接

https://leetcode.com/problems/minimum-size-subarray-sum/

题目描述

给定一个正整数数组nums和正整数target,找出nums中元素和大于等于target的最短子串,如果没有符合条件的子串,则返回0。

示例

输入:target = 7,nums = [2,3,1,2,4,3]

输出:2

子串[4,3]是满足条件的最短子串。
 

解题思路

此题求最短子串,可以由滑动窗口算法来求解。如果窗口内元素和小于target,则子串扩张,直到窗口内元素和大于等于target,找到一个可行解。然后右指针不动,左指针右移,去优化这个可行解,试图找到长度更短的子串。

注意要在确保找到一个可行解后更新结果,因此更新子串长度应该放在内层循环的开始,因为这样设置更新时能够保证当前窗口内元素和大于等于target。

Python实现

注意需要在最后判断res有没有更新,如果res仍等于float('inf'),说明nums中没有满足条件的子串,此时应当返回0。(要重视此类细节,即对于找不到符合条件的结果时如何返回)

class Solution:
    def minSubArrayLen(self, target: int, nums: List[int]) -> int:
        left,right = 0,0
        res = float('inf')
        cur_sum = 0
        while(right <len(nums)):
            s = nums[right]
            right += 1
            cur_sum += s
            while(cur_sum >= target):
                res = min(res,right-left)
                d = nums[left]
                left += 1
                cur_sum -= d
        return 0 if res == float('inf') else res
        

 

上一篇:AtCoder Beginner Contest 209 题解


下一篇:Ubuntu20.04安装ROS Noetic的小白教程