AlgoPressAppearance
0862-和至少为K的最短子数组
https://leetcode.cn/problems/shortest-subarray-with-sum-at-least-k
给你一个整数数组 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
思路(动态规划:Out of Memory)
动态规划， dp[i,j] 表示从i到j的和，当 dp[i,j] 为k的时候，记录 len = j-i+1，如果一直没找到，返回-1 dp[i,j] = dp[i,j-1]+nums[j] 初始化 dp[i,i] = nums[i]
注意：题目有坑，注意 “至少为K” ，应该是 >= K 而不是 == K，注意下面测试用例，输出为2，而不是3 [48,99,37,4,-31] 140
动态规划的方法最后会 Out Of Memory，说明数组开销太大，需要优化
参考代码
csharp
public class Solution {
public int ShortestSubarray(int[] nums, int k) {
int n = nums.Length;
int[,] dp = new int[n,n];
int minLength = int.MaxValue;
for(int i = 0; i < n; i++){
dp[i,i] = nums[i];
if(dp[i,i] >= k){
minLength = 1;
}
for(int j=i+1; j < n; j++){
dp[i,j] = dp[i,j-1]+nums[j];
//Console.WriteLine("dp[{0}{1}]={2}",i,j,dp[i,j]);
if(dp[i,j] >= k){
minLength = Math.Min(minLength,j-i+1);
}
}
}
return minLength == int.MaxValue ? -1 : minLength;
}
}
思路：滑动窗口(有问题)
模拟滑动窗口，当和大于k的时候，收缩窗口。
当有负数的时候有问题，测试用例 [84,-37,32,40,95] , 167 当滑动窗口为 [1..5] 的时候满足条件，此时长度为5， 但是收缩的时候，减去第一个数 84之后，就小于 167 了，所以不会继续收缩。 错过了答案 [3..5]
csharp
public class Solution {
public int ShortestSubarray(int[] nums, int k) {
//双指针
int left = 0 ;
int sum = 0;
int length = int.MaxValue;
for(int i=0; i<nums.Length; i++){
sum += nums[i];
while(sum >= k){
length = Math.Min(length, i-left+1);
//收缩
sum -= nums[left];
left++;
}
}
return length == int.MaxValue ? -1 : length;
}
}
思路2 【官方，单调队列】
使用 List 模拟双端队列， 会超时
csharp
public class Solution {
public int ShortestSubarray(int[] nums, int k) {
int n = nums.Length;
long[] preSum = new long[n+1];
//求前缀和
for(int i = 0; i < n; i++){
preSum[i+1] = preSum[i]+nums[i];
}
int ans = n+1; //答案不可能是 n+1，所以作为最大
List<int> list = new List<int>();
for(int j = 0; j < preSum.Length; j++){
while(list.Count > 0 && preSum[j] <= preSum[list[list.Count-1]]){
//移除最后一个
list.RemoveAt(list.Count-1);
}
while(list.Count > 0 && preSum[j] >= preSum[list[0]] + k){
int index = list[0];
list.RemoveAt(0);
ans = Math.Min(ans, j - index);
}
list.Add(j);
}
return ans < n + 1 ? ans : -1;
}
}
使用 LinkedList 模拟双端队列，不会超时
csharp
public class Solution{
public int ShortestSubarray(int[] nums, int k){
int n = nums.Length;
long[] preSum = new long[n+1]; //使用long型放置前缀和溢出
//求前缀和
for(int i=0; i<n; i++){
preSum[i+1] = nums[i]+preSum[i];
}
int ans = n + 1; //不需要设置 int.MaxValue
LinkedList<int> queue = new LinkedList<int>();
for(int j=0; j < preSum.Length; j++){
while(queue.Count > 0 && preSum[j] <= preSum[queue.Last.Value]){
queue.RemoveLast();
}
while(queue.Count > 0 && preSum[j] - preSum[queue.First.Value] >= k){
ans = Math.Min(ans, j - queue.First.Value);
queue.RemoveFirst();
}
queue.AddLast(j);
}
return ans == n + 1 ? -1 : ans;
}
}
备用 ： Java 队列提交, 之前 C# 使用 list 模拟会超时，使用 LinkedList 就不会超时了。
java
class Solution {
public int shortestSubarray(int[] A, int K) {
int N = A.length;
long[] P = new long[N+1];
for (int i = 0; i < N; ++i)
P[i+1] = P[i] + (long) A[i];
// Want smallest y-x with P[y] - P[x] >= K
int ans = N+1; // N+1 is impossible
Deque<Integer> monoq = new LinkedList(); //opt(y) candidates, as indices of P
for (int y = 0; y < P.length; ++y) {
// Want opt(y) = largest x with P[x] <= P[y] - K;
while (!monoq.isEmpty() && P[y] <= P[monoq.getLast()])
monoq.removeLast();
while (!monoq.isEmpty() && P[y] >= P[monoq.getFirst()] + K)
ans = Math.min(ans, y - monoq.removeFirst());
monoq.addLast(y);
}
return ans < N+1 ? ans : -1;
}
}
复习 双端队列：20220617
csharp
public class Solution {
public int ShortestSubarray(int[] nums, int k) {
//计算前缀和
int n = nums.Length;
long[] preSum = new long[n+1];
for(int i=0; i<n; i++){
preSum[i+1] = preSum[i] + nums[i];
}
//使用双端队列
LinkedList<int> queue = new LinkedList<int>();
int len = n + 1;
for(int j=0; j<preSum.Length; j++){
//区间和是 preSum[j]-preSum[i];
//如果当前面比前面后面的还小，说明更靠近后面的数，且和会更大，所以移除当前的最后一个数（我前面的那个数）
//原因是， 区间和 是 preSum[j]-preSum[i] ，所以当计算和的时候，如果后面的数减去前面那个数和能成立的话，那么减去我更加能成立，且长度更小，所以不需要前面的那个前缀和来参与计算
while(queue.Count > 0 && preSum[j] <= preSum[queue.Last.Value]){
queue.RemoveLast();
}
while(queue.Count > 0 && preSum[j] - preSum[queue.First.Value] >= k){
len = Math.Min(len, j - queue.First.Value);
queue.RemoveFirst();
}
queue.AddLast(j);
}
return len == n+1 ? -1 : len;
}
}