原題
給定一個(gè)由 n 個(gè)整數(shù)組成的數(shù)組和一個(gè)正整數(shù) s ，請(qǐng)找出該數(shù)組中滿足其和 ≥ s 的最小長(zhǎng)度子數(shù)組怒见。如果無解酱吝，則返回 -1。
樣例
給定數(shù)組 [2,3,1,2,4,3] 和 s = 7, 子數(shù)組 [4,3] 是該條件下的最小長(zhǎng)度子數(shù)組既绕。
解題思路
- 窗口類型題目 - 因?yàn)轭}目就是讓我們找到一個(gè)起點(diǎn)和一個(gè)終點(diǎn)，保證長(zhǎng)度最小且里面的數(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疲扎，但是長(zhǎng)度更長(zhǎng)，一定不是最優(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
