862 Shortest Subarray with Sum at Least K 和至少為 K 的最短子數(shù)組
Description:
Given an integer array nums and an integer k, return the length of the shortest non-empty subarray of nums with a sum of at least k. If there is no such subarray, return -1.
A subarray is a contiguous part of an array.
Example:
Example 1:
Input: nums = [1], k = 1
Output: 1
Example 2:
Input: nums = [1,2], k = 4
Output: -1
Example 3:
Input: nums = [2,-1,2], k = 3
Output: 3
Constraints:
1 <= nums.length <= 10^5
-10^5 <= nums[i] <= 10^5
1 <= k <= 10^9
題目描述:
返回 A 的最短的非空連續(xù)子數(shù)組的長度馍盟，該子數(shù)組的和至少為 K 。
如果沒有和至少為 K 的非空子數(shù)組忘朝，返回 -1 麻汰。
示例 :
示例 1：
輸入：A = [1], K = 1
輸出：1
示例 2：
輸入：A = [1,2], K = 4
輸出：-1
示例 3：
輸入：A = [2,-1,2], K = 3
輸出：3
提示:
1 <= A.length <= 50000
-10 ^ 5 <= A[i] <= 10 ^ 5
1 <= K <= 10 ^ 9
思路:
前綴和 + 單調(diào)隊列
由于題目要求求連續(xù)的子數(shù)組, 考慮使用滑動窗口, 但是因為數(shù)組中有負(fù)數(shù), 不滿足單調(diào)性, 所以不能使用滑動窗口
可以用類似滑動窗口的思想, 使用前綴和
因為需要求出子數(shù)組的和, 可以用前綴和預(yù)先處理, 方便查找子數(shù)組的和
假定已經(jīng)找到 i1 < i2 < j, pre[i1] >= pre[i2], 如果有 pre[j] - pre[i1] >= k, 那么一定有 pre[j] - pre[i2] >= k, 由于 i1 < i2, 所以 j - i1 > j - i2, 這時可以保證 i1 必然不是需要的值
所以需要一個單調(diào)隊列來存放, 遍歷到比隊列尾對應(yīng)的前綴和小的時候, 彈出隊尾
比如 [1, 3, -2, 4] -> [0, 1, 4, 2, 6], 6 - 2 > 6 - 4, 所以 4 應(yīng)該被彈出
按照滑動窗口的思想, 如果 pre[j] - pre[queue.front()] >= k, 這時可以彈出隊頭并且更新結(jié)果值
最后需要判斷是否存在結(jié)果滿足 k
時間復(fù)雜度為 O(n), 空間復(fù)雜度為 O(n)
代碼:
C++:
class Solution
{
public:
int shortestSubarray(vector<int>& nums, int k)
{
int n = nums.size(), result = n + 1;
vector<int> pre(n + 1, 0);
for (int i = 0; i < n; i++) pre[i + 1] = pre[i] + nums[i];
list<int> queue;
for (int i = 0; i <= n; i++)
{
while (!queue.empty() and pre[i] <= pre[queue.back()]) queue.pop_back();
while (!queue.empty() and pre[i] - pre[queue.front()] >= k)
{
result = min(result, i - queue.front());
queue.pop_front();
}
queue.push_back(i);
}
return result == n + 1 ? -1 : result;
}
};
Java:
class Solution {
public int shortestSubarray(int[] nums, int k) {
int n = nums.length, result = n + 1, pre[] = new int[n + 1];
for (int i = 0; i < n; i++) pre[i + 1] = pre[i] + nums[i];
LinkedList<Integer> queue = new LinkedList<>();
for (int i = 0; i <= n; i++) {
while (!queue.isEmpty() && pre[i] <= pre[queue.peekLast()]) queue.pollLast();
while (!queue.isEmpty() && pre[i] - pre[queue.peek()] >= k) result = Math.min(result, i - queue.poll());
queue.add(i);
}
return result == n + 1 ? -1 : result;
}
}
Python:
class Solution:
def shortestSubarray(self, nums: List[int], k: int) -> int:
pre, result, queue = [0] + list(accumulate(nums)), (n := len(nums)) + 1, deque()
for i, v in enumerate(pre):
while queue and v <= pre[queue[-1]]:
queue.pop()
while queue and v - pre[queue[0]] >= k:
result = min(result, i - queue.popleft())
queue.append(i)
return result if result < n + 1 else -1
