leetcode 209 长度最小的子数组

209. 长度最小的子数组

难度 中等

给定一个含有 n 个正整数的数组和一个正整数 s ，找出该数组中满足其和 ≥ s 的长度最小的连续子数组，并返回其长度。如果不存在符合条件的连续子数组，返回 0。

使用两个指针, 使用滑动窗口的思想, 当窗口内的数据之和小于target时, 右侧增加数据, 当窗口之内数据之和大于等于target时, 左侧减少数据, 直到右侧不能移动

第一个版本:

class Solution:
    def minSubArrayLen(self, s: int, nums: List[int]) -> int:
        ans = 0
        if sum(nums) < s:
            return ans
        ans = len(nums)
        left = 0
        right = 0
        betweensum = 0
        while right < len(nums):
            betweensum = sum(nums[left:right + 1]) # 最耗时的操作, 应修改
            if betweensum >= s:
                num = right - left + 1
                if num < ans:
                    ans = num
                left += 1
            else:
                right += 1
        return ans

第一个版本的结果是这样的

战胜了5%

上面已经提到, 最耗时的就是求和的操作, 其实每次的求和结果, 可以直接求下一次的求和结果, 不要这样不停地求和, 修改代码后如下:

class Solution:
    def minSubArrayLen(self, s: int, nums: List[int]) -> int:
        ans = 0
        if sum(nums) < s:
            return ans
        ans = len(nums)
        left = 0
        right = 0
        betweensum = 0
        betweensum = sum(nums[left:right + 1])

        while True:
            if betweensum >= s:
                num = right - left + 1
                if num < ans:
                    ans = num
                betweensum -= nums[left]
                left += 1
            else:
                right += 1
                if right == len(nums):
                    break
                betweensum += nums[right]
        return ans

我们把最初的求和操作放在循环外面, 这次求和结果可以求得下一次的结果