Leetcode练习(Python):数组类:第209题:给定一个含有 n 个正整数的数组和一个正整数 s ,找出该数组中满足其和 ≥ s 的长度最小的连续子数组。如果不存在符合条件的连续子数组,返回 0。

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

进阶:

如果你已经完成了O(n) 时间复杂度的解法, 请尝试 O(n log n) 时间复杂度的解法

思路:

双指针+滑动窗口

在一个小科技公司的面试时遇到过,当时手写代码写的很长很乱,看了网上的解答后记忆深刻。

程序:

class Solution:
    def minSubArrayLen(self, s: int, nums: List[int]) -> int:
        length = len(nums)
        if length <= 0:
            return 0
        if length == 1:
            if nums[0] >= s:
                return 1
            else:
                return 0
        head = 0
        auxiliary = 0
        result = float('inf')
        for tail in range(length):
            auxiliary += nums[tail]
            while auxiliary >= s:
                result = min(result, tail - head + 1)
                auxiliary -= nums[head]
                head += 1
        return result if result != float('inf') else 0
原文地址:https://www.cnblogs.com/zhuozige/p/12774549.html