Hard

题目描述

给你一个整数数组 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^5
  • -10^5 <= nums[i] <= 10^5
  • 1 <= k <= 10^9

解题思路

这道题是一个经典的滑动窗口问题，但由于数组中存在负数，传统的滑动窗口方法不适用。我们需要使用单调队列配合前缀和来解决。

核心思路：

  1. 前缀和转换：将问题转化为寻找两个位置 i < j，使得 prefixSum[j] - prefixSum[i] >= k，且 j - i 最小。

  2. 单调队列优化：维护一个单调递增的双端队列，存储前缀和的索引。队列中的前缀和值严格递增，这样可以确保对于每个位置 j，我们总是从最小的可能前缀和开始查找。

  3. 两个关键操作：

    • 当找到满足条件的子数组时，从队列头部弹出已使用的索引（因为后续更长的子数组不可能更优）
    • 当当前前缀和小于等于队列尾部的前缀和时，弹出尾部（因为当前位置更靠右，前缀和更小，更有潜力）

算法步骤：

  1. 计算前缀和数组
  2. 使用双端队列维护候选的起始位置索引
  3. 对每个位置，先尝试更新答案，再维护队列的单调性

时间复杂度为 O(n)，因为每个元素最多进出队列一次。

代码实现

class Solution {
public:
    int shortestSubarray(vector<int>& nums, int k) {
        int n = nums.size();
        vector<long long> prefixSum(n + 1, 0);
        
        // 计算前缀和
        for (int i = 0; i < n; i++) {
            prefixSum[i + 1] = prefixSum[i] + nums[i];
        }
        
        deque<int> dq;
        int result = INT_MAX;
        
        for (int i = 0; i <= n; i++) {
            // 尝试更新答案
            while (!dq.empty() && prefixSum[i] - prefixSum[dq.front()] >= k) {
                result = min(result, i - dq.front());
                dq.pop_front();
            }
            
            // 维护单调性
            while (!dq.empty() && prefixSum[i] <= prefixSum[dq.back()]) {
                dq.pop_back();
            }
            
            dq.push_back(i);
        }
        
        return result == INT_MAX ? -1 : result;
    }
};

class Solution:
    def shortestSubarray(self, nums: List[int], k: int) -> int:
        n = len(nums)
        prefix_sum = [0] * (n + 1)
        
        # 计算前缀和
        for i in range(n):
            prefix_sum[i + 1] = prefix_sum[i] + nums[i]
        
        from collections import deque
        dq = deque()
        result = float('inf')
        
        for i in range(n + 1):
            # 尝试更新答案
            while dq and prefix_sum[i] - prefix_sum[dq[0]] >= k:
                result = min(result, i - dq.popleft())
            
            # 维护单调性
            while dq and prefix_sum[i] <= prefix_sum[dq[-1]]:
                dq.pop()
            
            dq.append(i)
        
        return result if result != float('inf') else -1

public class Solution {
    public int ShortestSubarray(int[] nums, int k) {
        int n = nums.Length;
        long[] prefixSum = new long[n + 1];
        
        // 计算前缀和
        for (int i = 0; i < n; i++) {
            prefixSum[i + 1] = prefixSum[i] + nums[i];
        }
        
        var dq = new LinkedList<int>();
        int result = int.MaxValue;
        
        for (int i = 0; i <= n; i++) {
            // 尝试更新答案
            while (dq.Count > 0 && prefixSum[i] - prefixSum[dq.First.Value] >= k) {
                result = Math.Min(result, i - dq.First.Value);
                dq.RemoveFirst();
            }
            
            // 维护单调性
            while (dq.Count > 0 && prefixSum[i] <= prefixSum[dq.Last.Value]) {
                dq.RemoveLast();
            }
            
            dq.AddLast(i);
        }
        
        return result == int.MaxValue ? -1 : result;
    }
}

var shortestSubarray = function(nums, k) {
    const n = nums.length;
    const prefixSum = new Array(n + 1).fill(0);
    
    for (let i = 0; i < n; i++) {
        prefixSum[i + 1] = prefixSum[i] + nums[i];
    }
    
    const deque = [];
    let minLength = Infinity;
    
    for (let i = 0; i <= n; i++) {
        while (deque.length > 0 && prefixSum[i] - prefixSum[deque[0]] >= k) {
            minLength = Math.min(minLength, i - deque.shift());
        }
        
        while (deque.length > 0 && prefixSum[i] <= prefixSum[deque[deque.length - 1]]) {
            deque.pop();
        }
        
        deque.push(i);
    }
    
    return minLength === Infinity ? -1 : minLength;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度说明
时间复杂度O(n)每个元素最多进出队列一次
空间复杂度O(n)前缀和数组和双端队列的空间开销

相关题目