【leetcode】剑指 Offer II 008. 和大于等于 target 的最短子数组（滑动窗口，双指针）

剑指 Offer II 008. 和大于等于 target 的最短子数组

给定一个含有 n 个正整数的数组和一个正整数 target 。

找出该数组中满足其和 ≥ target 的长度最小的 连续子数组 $[num{s}_l,num{s}_{l+1},...,num{s}_{r-1},num{s}_r]$ ，并返回其长度。如果不存在符合条件的子数组，返回 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<=10^9$
• $1<=nums.length<=10^5$
• $1<=nums[i]<=10^5$

题解

滑动窗口

最简单的滑动窗口，不过这个超时了。

class Solution:
    def minSubArrayLen(self, target: int, nums: List[int]) -> int:
        for window_size in range(1, len(nums) + 1):
            for i in range(len(nums) + 1 - window_size):
                sum_window  = sum(nums[i: i + window_size])
                if sum_window >= target:
                    return window_size 
        return 0

改进（双指针）：
双指针left，right

class Solution:
    def minSubArrayLen(self, target: int, nums: List[int]) -> int:
        left = 0
        sum_window = 0
        min_len = 1e5 + 1
        for right, value in enumerate(nums):
            sum_window += value
            while sum_window >= target:
                min_len = min(min_len, right - left + 1)
                sum_window -= nums[left]
                left += 1
        return min_len if min_len <= 1e5 else 0

以 target = 7, nums = [2,3,1,2,4,3] 为例：

[2] 3  1  2  4  3    sum_window < target
[2  3] 1  2  4  3    sum_window < target
[2  3  1] 2  4  3    sum_window < target
[2  3  1  2] 4  3    sum_window >= target, min_len = 4 
 2 [3  1  2] 4  3    sum_window < target
 2 [3  1  2  4] 3    sum_window >= target, min_len = 4 
 2  3 [1  2  4] 3    sum_window >= target, min_len = 3 
 2  3  1 [2  4] 3    sum_window < target
 2  3  1 [2  4  3]   sum_window >= target, min_len = 3 
 2  3  1  2 [4  3]   sum_window >= target, min_len = 2
 2  3  1  2  4 [3]   sum_window < target