上海网站建设自学,网站营销中常见问题,知名企业网站规划书,网络推广专员招聘1. 题目
返回 A 的最短的非空连续子数组的长度#xff0c;该子数组的和至少为 K 。
如果没有和至少为 K 的非空子数组#xff0c;返回 -1 。
示例 1#xff1a;
输入#xff1a;A [1], K 1
输出#xff1a;1示例 2#xff1a;
输入#xff1a;A [1,2], K 4
输出该子数组的和至少为 K 。
如果没有和至少为 K 的非空子数组返回 -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来源力扣LeetCode 链接https://leetcode-cn.com/problems/shortest-subarray-with-sum-at-least-k 著作权归领扣网络所有。商业转载请联系官方授权非商业转载请注明出处。 2. 解题
类似题目 LeetCode 560. 和为K的子数组前缀和差分 LeetCode 523. 连续的子数组和求余 哈希 LeetCode 974. 和可被 K 整除的子数组哈希map
参考官方思路deque存储前缀和的下标队内前缀和需要严格单调递增跟队首的差值 k 时记录最小长度删除队首
class Solution {
public:int shortestSubarray(vectorint A, int K) {vectorint presum(A.size()1,0);int i, minLen INT_MAX, sum 0;dequeint q;//存储下标按照队内presum升序q.push_back(0);//边界条件前缀和为0下标为0for(i 0; i A.size(); i){presum[i1] presum[i] A[i];//前缀和while(!q.empty() presum[q.back()] presum[i1])q.pop_back();while(!q.empty() (presum[i1]-presum[q.front()] K)){minLen min(minLen, i1-q.front());q.pop_front();}q.push_back(i1);}if(minLen INT_MAX)return -1;return minLen;}
};
