HardRating 2307
862. Shortest Subarray with Sum at Least K
arraybinary-searchqueuesliding-windowheap-priority-queueprefix-summonotonic-queue
解題說明
Shortest Subarray with Sum at Least K
題目描述： 給定一個整數陣列 nums 和一個正整數 k，找出最短的非空子陣列，使其元素之和至少為 k。如果不存在這樣的子陣列，返回 -1。注意陣列中可能有負數。
解題思路：
- 前綴和 + 單調雙端佇列：由於有負數，不能用簡單的滑動窗口。改用前綴和把問題轉化為：找最短的 j - i 使得 prefix[j] - prefix[i] >= k。
- 維護一個遞增的雙端佇列（存前綴和的索引）。
- 對於每個位置 j，從佇列前端彈出滿足 prefix[j] - prefix[front] >= k 的元素（因為更後面的 j 不會更優）。
- 從佇列後端彈出所有 prefix >= prefix[j] 的元素（因為這些位置作為起點不如 j 優，j 更靠後且前綴和更小）。
- 將 j 加入佇列。
C++ 解法
複雜度分析
時間複雜度：O(n) — 每個索引最多入隊和出隊各一次
空間複雜度：O(n) — 前綴和陣列和雙端佇列
虛擬碼
1. Compute prefix sum array: prefix[0] = 0, prefix[i+1] = prefix[i] + nums[i]
2. Initialize monotonic deque (stores indices) and ans = infinity
3. For j from 0 to n:
a. While deque not empty AND prefix[j] - prefix[front] >= k:
- Update ans = min(ans, j - front)
- Pop front (this start index is consumed)
b. While deque not empty AND prefix[j] <= prefix[back]:
- Pop back (current j dominates as a start point)
c. Push j to back of deque
4. Return ans if <= n, else -1其他解法
-
二分搜尋 + 前綴和排序：對於每個 j，二分搜尋最大的 i 使得 prefix[j] - prefix[i] >= k。但需要維護前綴和的有序結構（如 BIT 或平衡 BST），時間複雜度 O(n log n)。
-
堆（Priority Queue）：將 (prefix[i], i) 放入最小堆。對每個 j，從堆頂取出最小前綴和嘗試配對。時間複雜度 O(n log n)，但實作較直覺。
延伸思考
- 如果所有數字都是正整數，如何簡化算法？（提示：滑動窗口）
- 如果要找的是和恰好等於 k 的最短子陣列呢？
- 如果改成找和至少為 k 的最長子陣列，該怎麼做？