209. Minimum Size Subarray Sum

给定一个包含n个正整数的数组和一个正整数s，找出其满足和sum ≥ s的子数组的最小长度。如果不存在这样的子数组，返回0

例如，给定数组 [2,3,1,2,4,3]与s = 7，
子数组[4,3]具有满足题设条件的最小长度。

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
26
27
class Solution(object):
    def minSubArrayLen(self, s, nums):
        """
        :type s: int
        :type nums: List[int]
        :rtype: int
        """
        # 7 star, 没能掌握，必须熟练掌握
        # 双指针，滑动窗口法
        # 双指针法，右指针不断往右遍历，如果左指针和右指针构成的子数组的和大于等于s了，左指针也开始往右遍历，意图寻找
        # 以右指针结尾且和大于等于s的子数组的最小长度，找到当前的最小长度左指针往前移动一步，右指针也继续往前直到和左指针构成的数组的和再次大于等于s,
        # 这时左指针又可以往前了，直到找到当前右指针为结尾的最小长度的子数组，一直这样重复，直到右指针到达数组的最右边
        if sum(nums) < s:
            return 0
        _min = 0xffffffff
        left, right = 0, 1
        cur = nums[0]
        while right < len(nums):
            while cur < s and right < len(nums):
                cur += nums[right]
                right += 1

            while cur >= s and left < right:
                cur -= nums[left]
                left += 1
            _min = min(_min, right - left + 1)
        return _min