原題

給定一個(gè)由 n 個(gè)整數(shù)組成的數(shù)組和一個(gè)正整數(shù) s ，請找出該數(shù)組中滿足其和 ≥ s 的最小長度子數(shù)組。如果無解，則返回 -1。

樣例
給定數(shù)組 [2,3,1,2,4,3] 和 s = 7, 子數(shù)組 [4,3] 是該條件下的最小長度子數(shù)組。

解題思路

• 窗口類型題目 - 因?yàn)轭}目就是讓我們找到一個(gè)起點(diǎn)和一個(gè)終點(diǎn)，保證長度最小且里面的數(shù)字之和不小于s
• 最自然的解法 - 雙層for循環(huán) - O(n2)的時(shí)間復(fù)雜度
• 優(yōu)化，前向型指針(追擊型指針)
• 第一點(diǎn)：因?yàn)閕 = 0, j = 3時(shí) 2 + 2 + 1 + 2 = 8 > 7，是一個(gè)candidate，之后我們不需要再向下遍歷，因?yàn)楹竺娑紩?huì)大于7，但是長度更長，一定不是最優(yōu)解，可以直接排除
• 第二點(diǎn)：在第一點(diǎn)的情況之后，要讓i = 1然后從j=i開始遍歷嗎?答案當(dāng)然是當(dāng)然不需要，因?yàn)閕= 0, j = 3時(shí)剛好sum > 7，所以i=1, j=2, i=1, j=3肯定都不需要考慮，可以直接讓j從剛剛的位置開始下一輪循環(huán)

完整代碼

class Solution(object):
    def minSubArrayLen(self, s, nums):
        """
        :type s: int
        :type nums: List[int]
        :rtype: int
        """
        right, sum = 0, 0
        res = sys.maxint
        for left in range(len(nums)):
            while right < len(nums) and sum < s:
                sum += nums[right]
                right += 1
            if sum >= s:
                res = min(res, right - left)
            sum -= nums[left]    
        if res == sys.maxint:
            return 0
        return res