What is the Minimum Size Subarray Sum problem?

The Minimum Size Subarray Sum problem asks you to find the minimal length of a contiguous subarray that has a sum greater than or equal to a given target.

How do you approach the Minimum Size Subarray Sum problem?

You can approach this problem using sliding window, binary search, and prefix sum techniques to efficiently find the smallest subarray that meets the target sum condition.

Why does binary search help in the Minimum Size Subarray Sum problem?

Binary search helps by narrowing down the search space for possible subarray lengths, allowing for faster optimization of the minimal subarray length.

What is the time complexity of the Minimum Size Subarray Sum solution?

The time complexity of the optimal solution is O(n), where n is the length of the input array.

How can GhostInterview assist in solving the Minimum Size Subarray Sum problem?

GhostInterview provides step-by-step guidance, highlights potential mistakes, and suggests efficient approaches like sliding window and binary search for solving this problem.

#209

Medium

auto_awesome二分·搜索·答案·空间

LeetCode 题解工作台

长度最小的子数组

给定一个含有 n 个正整数的数组和一个正整数 target 。找出该数组中满足其总和大于等于 target 的长度最小的子数组 [nums l , nums l+1 , ..., nums r-1 , nums r ] ，并返回其长度。如果不存在符合条件的子数组，返回 0 。示例 1：输…

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

题目描述

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

找出该数组中满足其总和大于等于 target 的长度最小的 子数组 [nums_l, nums_l+1, ..., nums_r-1, nums_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⁹
1 <= nums.length <= 10⁵
1 <= nums[i] <= 10⁴

进阶：

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

lightbulb

解题思路

方法一：前缀和 + 二分查找

我们先预处理出数组 $nums$ 的前缀和数组 $s$ ，其中 $s[i]$ 表示数组 $nums$ 前 $i$ 项元素之和。由于数组 $nums$ 中的元素都是正整数，因此数组 $s$ 也是单调递增的。另外，我们初始化答案 $ans = n + 1$ ，其中 $n$ 为数组 $nums$ 的长度。

接下来，我们遍历前缀和数组 $s$ ，对于其中的每个元素 $s[i]$ ，我们可以通过二分查找的方法找到满足 $s[j] \geq s[i] + target$ 的最小下标 $j$ ，如果 $j \leq n$ ，则说明存在满足条件的子数组，我们可以更新答案，即 $ans = min(ans, j - i)$ 。

最后，如果 $ans \leq n$ ，则说明存在满足条件的子数组，返回 $ans$ ，否则返回 $0$ 。

时间复杂度 $O(n \times \log n)$ ，空间复杂度 $O(n)$ 。其中 $n$ 为数组 $nums$ 的长度。

1

2

3

4

5

6

7

8

9

10

11

class Solution:
    def minSubArrayLen(self, target: int, nums: List[int]) -> int:
        n = len(nums)
        s = list(accumulate(nums, initial=0))
        ans = n + 1
        for i, x in enumerate(s):
            j = bisect_left(s, x + target)
            if j <= n:
                ans = min(ans, j - i)
        return ans if ans <= n else 0

speed

复杂度分析

指标	值
时间	O(n)
空间	O(1)

psychology

面试官常问的追问

外企场景

question_mark
The candidate demonstrates a solid understanding of sliding window techniques and can apply them to optimize the subarray sum problem.
question_mark
The candidate is familiar with binary search and can leverage it effectively for narrowing the search space.
question_mark
The candidate integrates prefix sums into their solution, showing they can optimize repetitive sum calculations.

warning

常见陷阱

外企场景

error
Overcomplicating the problem by trying to solve it without leveraging the sliding window or binary search techniques.
error
Failing to consider edge cases where no subarray satisfies the sum condition, leading to incorrect answers like returning a subarray length of zero when it should be zero.
error
Using brute force approaches that result in a time complexity of O(n^2) or worse, rather than utilizing O(n) algorithms.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Allowing negative numbers in the input array and adjusting the solution accordingly.
arrow_right_alt
Modifying the problem to return the subarray itself, not just its length.
arrow_right_alt
Changing the sum condition to be less than or equal to the target instead of greater than or equal to.

help

常见问题

外企场景

继续练习

#713 乘积小于 K 的子数组 #862 和至少为 K 的最短子数组 #1004 最大连续1的个数 III