1、题目
给定一个含有?n?个正整数的数组和一个正整数 target 。
找出该数组中满足其和 ≥ target 的长度最小的 连续子数组?[numsl, numsl+1, …, numsr-1, numsr] ，并返回其长度。如果不存在符合条件的子数组，返回 0 。
示例 1：
输入：target = 7, nums = [2,3,1,2,4,3]
输出：2
解释：子数组 [4,3] 是该条件下的长度最小的子数组。
2、解答
- 暴力法：遍历数组，固定子数组的第一个元素，然后再遍历之后的元素，计算子数组和，不小于target时，比较子数组长度和已经获得最短子数组长度。
- 滑动窗口法：维护一前一后两个指针，指针间的距离是窗口长度，
当窗口内元素和小于target的是，窗口右指针向右滑动，
当小于target的时候，窗口左指针向右滑动。
def minSubArrayLen(self, target, nums):
"""
暴力法：
:type target: int
:type nums: List[int]
:rtype: int
"""
if not nums:
return 0
res = len(nums) + 1
for i in range(len(nums)):
total = nums[i]
if total >= target:
res = 1
break
else:
for j in range(i + 1, len(nums)):
total += nums[j]
if total >= target:
res = min(res, j - i + 1)
break
return 0 if res == len(nums) + 1 else res
def minSubArrayLen2(self, target, nums):
"""
滑动窗口法：维护一前一后两个指针，指针间的距离是窗口长度
当窗口内元素和小于target的是，窗口右指针向右滑动
当小于target的时候，窗口左指针向右滑动
:type target: int
:type nums: List[int]
:rtype: int
"""
if not nums:
return 0
res = len(nums) + 1
i = 0
while i < len(nums):
j = i
while i <= j and j <= len(nums) - 1:
total = sum(nums[i:j + 1])
if total < target:
j += 1
else:
res = min(res, j - i + 1)
i += 1
if j > len(nums) - 1:
break
return 0 if res == len(nums) + 1 else res
|