插： 前些天發(fā)現(xiàn)了一個巨牛的人工智能學(xué)習(xí)網(wǎng)站悍募，通俗易懂蘑辑，風(fēng)趣幽默，忍不住分享一下給大家坠宴。點擊跳轉(zhuǎn)到網(wǎng)站洋魂。
堅持不懈，越努力越幸運喜鼓，大家一起學(xué)習(xí)鴨~~~
3妹
3妹：小呀么小二郎呀副砍， 背著那書包上學(xué)堂。
2哥：不怕太陽曬庄岖， 不怕那風(fēng)雨打豁翎。
3妹：就怕老師說我懶呀，沒有學(xué)問隅忿，無臉見爹娘心剥。
2哥：3妹, 周杰倫又發(fā)新專輯了，you know? 你的曲庫該更新一下了背桐。
3妹：yeah, I know. 我可是聽著我倫的歌長大的优烧。
2哥：是的， 記得那時還是上高中的時候……
3妹：2哥链峭，又開始回憶你的青春歲月了畦娄，哈哈
2哥：3妹也會取笑人了，不跟你說了，我繼續(xù)做題了熙卡。
講課
題目：
給你一個整數(shù)數(shù)組 nums 和一個整數(shù) k 杖刷，找出 nums 中和至少為 k 的 最短非空子數(shù)組 ，并返回該子數(shù)組的長度驳癌。如果不存在這樣的 子數(shù)組 滑燃，返回 -1 。
子數(shù)組 是數(shù)組中 連續(xù) 的一部分喂柒。
示例 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
-105 <= nums[i] <= 10^5
1 <= k <= 10^9
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;
}
}
