LeetCode - 209. Minimum Size Subarray Sum

题目描述

Given an array of positive integers nums and a positive integer target, return the minimal length of a subarray whose sum is greater than or equal to target. If there is no such subarray, return 0 instead.

Example 1:

1
2
3

Input: target = 7, nums = [2,3,1,2,4,3]
Output: 2
Explanation: The subarray [4,3] has the minimal length under the problem constraint.

Example 2:

1 2	Input: target = 4, nums = [1,4,4] Output: 1

Example 3:

1 2	Input: target = 11, nums = [1,1,1,1,1,1,1,1] Output: 0

Constraints:

1 <= target <= 10^9
1 <= nums.length <= 10^5
1 <= nums[i] <= 10^4

Follow up: If you have figured out the O(n) solution, try coding another solution of which the time complexity is O(n log(n)).

解题方法

双指针

思路解析：

滑动窗口：使用两个指针 left 和 right 来维护一个窗口，right 用来扩展窗口，left 用来缩小窗口。
窗口内求和：随着 right 的移动，我们将元素加入窗口，并计算窗口内的和。当窗口内的和大于等于 target 时，尝试移动 left 来缩小窗口，并更新最小长度。
不断更新最小长度：每次找到满足条件的窗口后，记录该窗口的长度，并继续尝试找到更短的窗口。

具体步骤：

初始化：left 指针设为 0，right 指针从 0 开始，sum 初始化为 0，min_length 初始化为正无穷大。
扩展窗口：遍历数组，每次将 nums[right] 加到 sum 中。
缩小窗口：当 sum 大于等于 target 时，更新 min_length 为 right - left + 1，并尝试通过移动 left 来缩小窗口，同时减少 sum 的值。
重复步骤 2 和 3，直到遍历完整个数组。
最后，如果 min_length 仍为正无穷大，说明没有找到符合条件的子数组，返回 0；否则，返回 min_length。

class Solution:
    def minSubArrayLen(self, target: int, nums: List[int]) -> int:
        left = 0
        sum = 0
        min_length = float('inf')
        
        for right in range(len(nums)):
            sum += nums[right]
            
            while sum >= target:
                min_length = min(min_length, right - left + 1)
                sum -= nums[left]
                left += 1
        
        return 0 if min_length == float('inf') else min_length

时间复杂度：$O(n)$

空间复杂度：$O(1)$

二分查找

使用二分查找可以将问题的时间复杂度提升到 O(n log n)。这种方法基于前缀和（Prefix Sum）与二分查找的结合。

思路解析：

前缀和数组：
- 首先，构建一个前缀和数组 prefix_sums，其中 prefix_sums[i] 表示数组 nums 前 i 个元素的和。即 prefix_sums[i] = nums[0] + nums[1] + ... + nums[i-1]。
- 因此，任何子数组 nums[i...j] 的和可以表示为 prefix_sums[j+1] - prefix_sums[i]。
二分查找：
- 对于每一个起点 i，我们希望找到最小的 j 使得 prefix_sums[j+1] - prefix_sums[i] >= target。这等价于在 prefix_sums 中找到最小的 j，使得 prefix_sums[j+1] >= prefix_sums[i] + target。
- 通过二分查找，可以在 prefix_sums 数组中快速找到这个 j。
更新最小长度：
- 对每一个起点 i，如果找到了满足条件的 j，我们更新最小子数组长度为 j - i + 1。

具体步骤：

构建前缀和数组 prefix_sums，长度为 n + 1，其中 prefix_sums[0] = 0。
遍历数组 nums 的每一个起点 i，计算当前需要查找的目标和 target_sum = prefix_sums[i] + target。
使用二分查找在 prefix_sums 中查找最小的 j 使得 prefix_sums[j] >= target_sum。
更新最小子数组长度为 j - i，如果找到了符合条件的 j。
最后返回最小子数组长度，如果没有找到则返回 0。

class Solution:
    def minSubArrayLen(self, target: int, nums: List[int]) -> int:
        n = len(nums)
        prefix_sums = [0] * (n + 1)
        
        # 构建前缀和数组
        for i in range(1, n + 1):
            prefix_sums[i] = prefix_sums[i - 1] + nums[i - 1]
        
        min_length = float('inf')
        
        # 遍历数组查找最小子数组长度
        for i in range(n):
            target_sum = prefix_sums[i] + target
            # 二分查找最小的j使得prefix_sums[j] >= target_sum
            j = bisect.bisect_left(prefix_sums, target_sum)
            if j <= n:
                min_length = min(min_length, j - i)
        
        return 0 if min_length == float('inf') else min_length

时间复杂度：$O(nlogn)$

空间复杂度：$O(n)$