LeetCode 862. 和至少为 K 的最短子数组

Categories:

题目描述
思路分析
1. 解法一：前缀和 + 单调双端队列（推荐）
2. 解法二：前缀和 + 有序集合（堆）
相似题目

题目描述

✅ 862. 和至少为 K 的最短子数组

思路分析

解法一：前缀和 + 单调双端队列（推荐）

核心思路：

若数组中只含正数，可以直接用滑动窗口；但本题数组含负数，子数组和不具备单调性，滑动窗口失效。

构造前缀和数组 prefix，问题转化为：找最小的 i - j，使得 prefix[i] - prefix[j] >= k（i > j）。

维护一个 单调递增 的双端队列，队列中存前缀和的下标。

外层遍历 i（右端点），当队首 j 满足 prefix[i] - prefix[j] >= k 时，更新最短长度并弹出队首（因为后续 i 更大，队首已是最优，可以出队）。

维护单调性：将当前 i 入队前，弹出所有 prefix 值 >= prefix[i] 的队尾（它们不可能作为更优的左端点）。

复杂度分析：

时间复杂度：O(n)，其中 n 为数组长度，每个下标最多入队和出队各一次。

空间复杂度：O(n)，前缀和数组与双端队列各占 O(n) 空间。

import java.util.ArrayDeque;
import java.util.Deque;

class Solution {
    public int shortestSubarray(int[] nums, int k) {
        int n = nums.length;
        // 构造前缀和数组，长度为 n+1，prefix[0] = 0
        long[] prefix = new long[n + 1];
        for (int i = 0; i < n; i++) {
            prefix[i + 1] = prefix[i] + nums[i];
        }

        int ans = Integer.MAX_VALUE;
        // 单调递增双端队列，存前缀和下标
        Deque<Integer> deque = new ArrayDeque<>();

        for (int i = 0; i <= n; i++) {
            // 队首满足条件时，更新答案并出队
            while (!deque.isEmpty() && prefix[i] - prefix[deque.peekFirst()] >= k) {
                ans = Math.min(ans, i - deque.pollFirst());
            }
            // 维护单调递增：弹出所有 prefix 值 >= 当前值的队尾
            while (!deque.isEmpty() && prefix[deque.peekLast()] >= prefix[i]) {
                deque.pollLast();
            }
            deque.offerLast(i);
        }

        return ans == Integer.MAX_VALUE ? -1 : ans;
    }
}

func shortestSubarray(nums []int, k int) int {
    n := len(nums)
    // 构造前缀和数组，长度为 n+1，prefix[0] = 0
    prefix := make([]int64, n+1)
    for i, v := range nums {
        prefix[i+1] = prefix[i] + int64(v)
    }

    ans := math.MaxInt32
    // 单调递增双端队列，存前缀和下标
    deque := make([]int, 0, n+1)

    for i := 0; i <= n; i++ {
        // 队首满足条件时，更新答案并出队
        for len(deque) > 0 && prefix[i]-prefix[deque[0]] >= int64(k) {
            if i-deque[0] < ans {
                ans = i - deque[0]
            }
            deque = deque[1:]
        }
        // 维护单调递增：弹出所有 prefix 值 >= 当前值的队尾
        for len(deque) > 0 && prefix[deque[len(deque)-1]] >= prefix[i] {
            deque = deque[:len(deque)-1]
        }
        deque = append(deque, i)
    }

    if ans == math.MaxInt32 {
        return -1
    }
    return ans
}

解法二：前缀和 + 有序集合（堆）

核心思路：

同样基于前缀和，对于每个右端点 i，需要找满足 prefix[j] <= prefix[i] - k 的最大 j（最近的左端点），以使子数组最短。

使用最小堆（优先队列）存储 (prefix[j], j) 对，遍历到 i 时弹出所有 prefix[j] <= prefix[i] - k 的堆顶，取下标最大的更新答案。

该方法时间复杂度为 O(n log n)，不如解法一，适合作为备选思路理解。

复杂度分析：

时间复杂度：O(n log n)，其中 n 为数组长度，每次堆操作为 O(log n)。

空间复杂度：O(n)，堆中最多存 n+1 个元素。

import java.util.PriorityQueue;

class Solution {
    public int shortestSubarray(int[] nums, int k) {
        int n = nums.length;
        // 构造前缀和数组
        long[] prefix = new long[n + 1];
        for (int i = 0; i < n; i++) {
            prefix[i + 1] = prefix[i] + nums[i];
        }

        int ans = Integer.MAX_VALUE;
        // 最小堆，按前缀和升序排列，存 (prefixSum, index)
        PriorityQueue<long[]> minHeap = new PriorityQueue<>((a, b) -> Long.compare(a[0], b[0]));

        for (int i = 0; i <= n; i++) {
            // 弹出所有满足条件的堆顶，取下标最大值更新答案
            while (!minHeap.isEmpty() && prefix[i] - minHeap.peek()[0] >= k) {
                ans = Math.min(ans, i - (int) minHeap.poll()[1]);
            }
            minHeap.offer(new long[]{prefix[i], i});
        }

        return ans == Integer.MAX_VALUE ? -1 : ans;
    }
}

import "container/heap"

// 最小堆辅助类型
type minHeap [][]int64

func (h minHeap) Len() int            { return len(h) }
func (h minHeap) Less(i, j int) bool  { return h[i][0] < h[j][0] }
func (h minHeap) Swap(i, j int)       { h[i], h[j] = h[j], h[i] }
func (h *minHeap) Push(x interface{}) { *h = append(*h, x.([]int64)) }
func (h *minHeap) Pop() interface{} {
    old := *h
    n := len(old)
    x := old[n-1]
    *h = old[:n-1]
    return x
}

func shortestSubarray(nums []int, k int) int {
    n := len(nums)
    // 构造前缀和数组
    prefix := make([]int64, n+1)
    for i, v := range nums {
        prefix[i+1] = prefix[i] + int64(v)
    }

    ans := math.MaxInt32
    h := &minHeap{}
    heap.Init(h)

    for i := 0; i <= n; i++ {
        // 弹出所有满足条件的堆顶，更新最短长度
        for h.Len() > 0 && prefix[i]-(*h)[0][0] >= int64(k) {
            top := heap.Pop(h).([]int64)
            if idx := int(top[1]); i-idx < ans {
                ans = i - idx
            }
        }
        heap.Push(h, []int64{prefix[i], int64(i)})
    }

    if ans == math.MaxInt32 {
        return -1
    }
    return ans
}

相似题目

题目	难度	考察点
209. 长度最小的子数组	中等	滑动窗口、前缀和
239. 滑动窗口最大值	困难	单调队列
1438. 绝对差不超过限制的最长连续子数组	中等	单调队列、滑动窗口
918. 环形子数组的最大和	中等	前缀和、单调队列
1499. 满足不等式的最大值	困难	单调队列、滑动窗口
53. 最大子数组和	中等	前缀和、动态规划

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2025/33647923