LeetCode刷题之路：209. 长度最小的子数组_给一个数组和target值,找出长度最长的且和等于target的连续子数组的长 度

如果帮助到您，还请点个关注吧，hahaha

给定一个含有 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 = 4, nums = [1,4,4]
输出：1
示例 3：

输入：target = 11, nums = [1,1,1,1,1,1,1,1]
输出：0

提示：

1 <= target <= 109
1 <= nums.length <= 105
1 <= nums[i] <= 105

#最直观的思路
可以使用两个for循环进行暴力求解，只不过时间复杂度过高。

#双指针思路
可以设定两个指针，这两个指针便可以代表子序列的起始位置和终止位置。
最初起始位置j为0，让子数组的终止位置向前移动，
直至子数组中所有数的和大于等于目标值，
判断当前子数组的长度是否小于目前最优的结果，如果小于，则更新结果
sum1 -= nums[j]
j += 1
随后这两步是这道题的关键之处，
我们让当前和减去子数组中的第一个数，并更新起始位置的指针+1，
如果当前子数组中所有数的和仍大于目标值，
则更新结果，同时接着重复上面的操作。
直至和小于目标值，随后我们再移动终止位置的指针，重复以上过程
直到遍历完整个数组

class Solution:
    def minSubArrayLen(self, target: int, nums: List[int]) -> int:
        j = 0
        result = 100000
        sum1 = 0
        for i in range(len(nums)):
            sum1 += nums[i]
            while sum1 >= target:
                length = i - j + 1
                if length < result:
                    result = length
                sum1 -= nums[j]
                j += 1
        if result != 100000:
            return result
        else: 
			return 0

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18