0209 Python更容易理解时间复杂度的版本

[LogicFan]

也是使用滑动窗口方法.

class Solution:
    def minSubArrayLen(self, target: int, nums: List[int]) -> int:
        i = 0
        j = 0
        s = 0
        r = len(nums) + 1 # a sufficient large number to indicate no result
        while True:
            if s < target:
                if j == len(nums):
                    break
                s += nums[j]
                j += 1
            else:
                r = min(r, j - i)
                s -= nums[i]
                i += 1
        
        if r == len(nums) + 1:
            return 0
        else:
            return r

这是我做题的时候写的, 因为不涉及到两个loop嵌套, 在分析时间复杂度的时候更加容易.

证明: 因为nums和target均为正数, 则 i <= j (loop invariant), 而在j到达len(nums)循环停止, 则循环内最多执行2 * len(nums)次.

有点懒惰开fork了, 那位好心人看到觉得有价值的和帮忙开个PR吧.