长度最小的子数组
给定一个含有 n 个正整数的数组和一个正整数 target 。
找出该数组中满足其和 ≥ target 的长度最小的 连续子数组 [numsl, numsl+1, ..., numsr-1, numsr] ，并返回其长度。如果不存在符合条件的子数组，返回 0 。
示例 1：
输入：target = 7, nums = [2,3,1,2,4,3]
输出：2
解释：子数组 [4,3] 是该条件下的长度最小的子数组。
Python
解一（会超出时间限制）：
class Solution(object):
def minSubArrayLen(self, target, nums):
"""
:type target: int
:type nums: List[int]
:rtype: int
"""
result_final = []
tim = 0
for t in range(len(nums)):
sum = 0
flag = 0
for i in nums[t:]:
sum += i
flag += 1
if sum >= target:
result_final.append(flag)
break
if result_final == []:
return 0
else:
return min(result_final)
解二：
class Solution(object):
def minSubArrayLen(self, target, nums):
"""
:type target: int
:type nums: List[int]
:rtype: int
"""
first = 0
result = float('inf')
num = 0
for end in range(len(nums)):
num = num + nums[end]
while num >= target:
result = min(result,end - first+1)
num = num - nums[first]
first += 1
return 0 if result == float('inf') else result
笔记
- 暴力求解（即解一），时间复杂度较高，会超出时间限制；
- 采用滑动窗口法（双指针法），两个指针一个指向所求区间尾端（end），另一个指向所求区间首段（first），根据题意要求的是最小的能使其和大于等于target的区间，因此当区间内和小于target时尾端应该右移，扩大区间，当区间内和大于等于target时，首端应右移，减少区间内元素个数。