一、题目

给定一个含有 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

进阶：

如果你已经实现 O(n) 时间复杂度的解法, 请尝试设计一个 O(n log(n)) 时间复杂度的解法。

三、解法

解法1 暴力解法

#时间：O(n^2)
#空间：O(1)
class Solution:
    def minSubArrayLen(self, target: int, nums: List[int]) -> int:
        l = 1
        n = len(nums)
        while l <= n:
            left = 0
            temp = sum(nums[left:left+l])
            while left + l <= n:
                if left != 0:
                    temp += nums[left+l-1]
                if  temp >= target:
                    return l
                temp -= nums[left]
                left += 1
            l += 1
        return 0

最后一个case不能通过

解法2 双指针

#时间：O(n)
#空间：O(1)
class Solution:
    def minSubArrayLen(self, target: int, nums: List[int]) -> int:
        #初始化
        n = len(nums)
        left , right , res = 0 , 0 , n+1
        tempSum = 0
        while right < n :
            tempSum += nums[right]
            while tempSum >= target:
                res = min(res,right - left + 1)
                tempSum -= nums[left]
                left += 1
            right += 1
        return res if res != n+1 else 0

四、思考

遇到连续的问题，可以采用滑动窗口去计算，第二层循环也可以写为if语句配合continue。

目前，对数组类的题目有了全新的解题角度。

2021年4月4日13:47:10