长度最小的子数组

标签: 数组 二分查找 前缀和 滑动窗口

难度: Medium

给定一个含有 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)) 时间复杂度的解法。

注意：本题与主站 209 题相同：https://leetcode-cn.com/problems/minimum-size-subarray-sum/

Submission

运行时间: 26 ms

内存: 17.7 MB

class Solution:
    def minSubArrayLen(self, target, nums):
        left = total = 0
        ret = float('inf')
        for right, num in enumerate(nums):
            total += num
            while total >= target:
                ret = min(ret, right - left + 1)
                total -= nums[left]
                left += 1
        return 0 if ret > len(nums) else ret

Explain

这个题解采用了滑动窗口（双指针）的方法，来寻找数组中的最小连续子数组，其和大于等于给定的target。方法中，我们定义两个指针left和right，表示子数组的左右边界。从头开始遍历数组，逐渐扩展right指针来增加子数组的和。每当子数组的和达到或超过target时，尝试通过移动left指针来缩小窗口大小，直到子数组的和小于target。在此过程中，我们记录达到条件的最小子数组长度。整个过程中，每个元素只会被访问两次（一个添加到窗口，一个从窗口中移除），因此时间效率较高。

时间复杂度: O(n)

空间复杂度: O(1)

# 定义解决问题的类

class Solution:
    def minSubArrayLen(self, target, nums):
        left = total = 0  # 初始化左指针和当前和
        ret = float('inf')  # 用来存储最小长度的变量，初始设为无穷大
        # 遍历数组元素，使用right作为右指针
        for right, num in enumerate(nums):
            total += num  # 将当前元素加到总和上
            # 当总和大于等于目标值时，尝试缩小窗口以找到可能的更小长度
            while total >= target:
                ret = min(ret, right - left + 1)  # 更新最小长度
                total -= nums[left]  # 从总和中减去左边界的值
                left += 1  # 移动左指针
        # 如果没有找到有效的子数组，返回0；否则返回找到的最小长度
        return 0 if ret > len(nums) else ret

Explore

当总和达到或超过目标值target时，继续增加右边界只会进一步增加子数组的长度，这与寻找最小长度的目标相悖。通过缩小左边界（即移动left指针向右），我们可以尝试减小数组的长度而不是增加，从而找到可能的最小长度满足条件的子数组。

即使总和刚好等于target，我们仍然尝试缩小窗口是为了探索是否存在更小的符合条件的子数组。可能存在某些元素的值较大，导致移动左指针后，即使减少了一些元素，总和仍然能满足条件。这样，我们可以确保找到的是真正的最小长度子数组。

有必要遍历整个数组，因为我们无法事先知道数组的总和是否达到target，除非遍历完所有元素。此外，即使在遍历的过程中总和一度未达到target，我们也需要确认这一点以确实不存在任何子数组能满足条件，从而准确返回0。