209. Minimum Size Subarray Sum

Posted on | Edited on | In , |

题目

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

想法

逐个遍历，然后保存最小的序列？是不是想得太简单点了，复杂度的话，O(n^2)，这应该是上界，一般不会这会多吧

答案

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution(object):
    def minSubArrayLen(self, s, nums):
        """
        :type s: int
        :type nums: List[int]
        :rtype: int
        """
        if not nums:
            return 0
        sum = 0
        sum += nums[0]
        if sum > s:
            return 1
        a = 0
        ans = sys.maxsize
        for b in range(1, len(nums)):
            sum += nums[b]
            while sum >= s:
                ans = min(ans, b - a + 1)
                sum -= nums[a]
                a += 1
        if ans == sys.maxsize:
            return 0
        else:
            return ans

回顾

准确的复杂度自己也说不清楚，应该能得到一个上界小于O(n^2)