题目

给定一个含有 n 个正整数的数组和一个正整数 s，找出该数组中满足其和 ≥ s 的长度最小的连续子数组。如果不存在符合条件的连续子数组，返回 0。

示例:

  1. 输入: s = 7, nums = [2,3,1,2,4,3]
  2. 输出: 2
  3. 解释: 子数组 [4,3] 是该条件下的长度最小的连续子数组。

方案一

def minSubArrayLen(self, s: int, nums: [int]) -> int:
    # 下述算法思路相似，代码不同，可能更好理解
    if not nums: return 0
    left = 0
    cur = 0
    res = float("inf")
    for right in range(len(nums)):
        cur += nums[right]
        while cur >= s:
            res = min(res, right - left + 1)
            cur -= nums[left]
            left += 1
    return res if res != float("inf") else 0

方案二（双指针）

class Solution:
    def minSubArrayLen(self, s: int, nums: List[int]) -> int:
        if not nums:
            return 0
        res = float('inf')
        i, j = 0, 1
        i_j_count = nums[0]
        while i < j and j <= len(nums):
            if i_j_count < s:
                if j < len(nums): i_j_count += nums[j]
                j += 1
            else:
                res = min(res, j - i)
                i_j_count -= nums[i]
                i += 1

        return res if res != float('inf') else 0
  • 两个指针内的和要大于给定值；
  • 关键点在如何移动这两个指针；
    1. 首先移动右指针，同时区间内的和；
    2. 当满足条件时候，左指针往前移动；
    3. 一直到右指针移动到越界，同时左指针也不能移动为止；
    4. 移动期间记录最小的长度。

记录指针范围内和，而不是每次都求一次两个指针范围内数值之和是为了减少时间复杂度。

原文

https://leetcode-cn.com/explore/featured/card/array-and-string/201/two-pointer-technique/789/