What is the main pattern used in the Shortest Subarray with Sum at Least K problem?

The primary pattern used in this problem is binary search over the valid answer space, combined with sliding window and monotonic queue techniques.

How do you handle negative numbers in the array for this problem?

Negative numbers complicate the use of sliding windows but can be managed by ensuring the prefix sum is computed and adjusted correctly, leveraging the monotonic queue to maintain order.

Why is binary search used in this problem?

Binary search is applied to find the minimal subarray length by searching over the valid answer space, optimizing the solution's efficiency.

What happens if there’s no valid subarray with sum at least k?

If no valid subarray is found, the solution should return -1, indicating that it’s impossible to form such a subarray.

Can the solution be optimized further beyond O(n) time complexity?

The solution using binary search, sliding window, and monotonic queue achieves the optimal O(n) time complexity, and further optimizations are unlikely.

#862

Hard

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

LeetCode 题解工作台

和至少为 K 的最短子数组

给你一个整数数组 nums 和一个整数 k ，找出 nums 中和至少为 k 的最短非空子数组，并返回该子数组的长度。如果不存在这样的子数组，返回 -1 。子数组是数组中连续的一部分。示例 1：输入： nums = [1], k = 1 输出： 1 示例 2：输入： nums …

数组二分查找队列滑动窗口堆（优先队列）

题目描述

给你一个整数数组 nums 和一个整数 k ，找出 nums 中和至少为 k 的 最短非空子数组 ，并返回该子数组的长度。如果不存在这样的 子数组 ，返回 -1 。

子数组 是数组中连续的一部分。

示例 1：

输入：nums = [1], k = 1
输出：1

示例 2：

输入：nums = [1,2], k = 4
输出：-1

示例 3：

输入：nums = [2,-1,2], k = 3
输出：3

提示：

1 <= nums.length <= 10⁵
-10⁵ <= nums[i] <= 10⁵
1 <= k <= 10⁹

lightbulb

解题思路

方法一：前缀和 + 单调队列

题目要求找到一个最短的子数组，使得子数组的和大于等于 $k$ 。不难想到，可以使用前缀和快速计算子数组的和。

我们用一个长度为 $n+1$ 的数组 $s[i]$ 表示数组 $nums$ 前 $i$ 个元素的和。另外，我们需要维护一个严格单调递增的队列 $q$ ，队列中存储的是前缀和数组 $s[i]$ 的下标。注意，这里的单调递增是指下标对应的前缀和的大小，而不是下标的大小。

为什么存的是下标呢？这是为了方便计算子数组的长度。那为什么队列严格单调递增？我们可以用反证法来说明。

假设队列元素非严格单调递增，也即是说，存在下标 $i$ 和 $j$ ，满足 $i < j$ ，且 $s[i] \geq s[j]$ 。

当遍历到下标 $k$ ，其中 $i \lt j \lt k \leq n$ ，此时 $s[k]-s[j] \geq s[k]-s[i]$ ，且 $nums[j..k-1]$ 的长度小于 $nums[i..k-1]$ 的长度。由于下标 $j$ 的存在，子数组 $nums[i..k-1]$ 一定不是最优解，队列中的下标 $i$ 是不必要的，需要将其移除。因此，队列中的元素一定严格单调递增。

回到这道题目上，我们遍历前缀和数组 $s$ ，对于遍历到的下标 $i$ ，如果 $s[i] - s[q.front] \geq k$ ，说明当前遇到了一个可行解，我们可以更新答案。此时，我们需要将队首元素出队，直到队列为空或者 $s[i] - s[q.front] \lt k$ 为止。

如果此时队列不为空，为了维持队列的严格单调递增，我们还需要判断队尾元素是否需要出队，如果 $s[q.back] \geq s[i]$ ，则需要循环将队尾元素出队，直到队列为空或者 $s[q.back] \lt s[i]$ 为止。然后，我们将下标 $i$ 入队。

遍历结束，如果我们没有找到可行解，那么返回 $-1$ 。否则，返回答案。

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

1

2

3

4

5

6

7

8

9

10

11

12

13

class Solution:
    def shortestSubarray(self, nums: List[int], k: int) -> int:
        s = list(accumulate(nums, initial=0))
        q = deque()
        ans = inf
        for i, v in enumerate(s):
            while q and v - s[q[0]] >= k:
                ans = min(ans, i - q.popleft())
            while q and s[q[-1]] >= v:
                q.pop()
            q.append(i)
        return -1 if ans == inf else ans

speed

复杂度分析

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

psychology

面试官常问的追问

外企场景

question_mark
Ensure the candidate can efficiently optimize their solution using binary search and sliding window techniques.
question_mark
Look for the use of prefix sums and monotonic queues to avoid unnecessary recalculations.
question_mark
Evaluate their ability to recognize when a solution needs binary search over a valid answer space.

warning

常见陷阱

外企场景

error
Misunderstanding the need for binary search over answer space, which is crucial for optimizing the solution.
error
Forgetting to properly handle the case where no subarray satisfies the sum condition, leading to a wrong answer.
error
Not managing the monotonic queue properly, which can lead to inefficiency or incorrect results.

swap_horiz

进阶变体

外企场景

arrow_right_alt
What happens if the array contains negative numbers? How does this affect the sliding window approach?
arrow_right_alt
Can this problem be solved using a brute force approach, and what are the trade-offs?
arrow_right_alt
How does the time complexity change if we used a naive method instead of binary search and sliding window?

help

常见问题

外企场景

继续练习

#2398 预算内的最多机器人数目 #1425 带限制的子序列和 #1438 绝对差不超过限制的最长连续子数组