数据结构
网络
关系数据库管理系统(RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装学
法学C++中求和至少为K的最短子数组
假设我们有一个数组A。我们需要找到A的最短非空连续子数组的长度，其和至少为K。如果没有这样的子数组，则返回-1。
因此，如果输入类似于[5,3,-2,2,1]并且k = 6，则输出将为2，因为我们可以看到(5+3) >= 6
为了解决这个问题，我们将遵循以下步骤：
n := A的大小
ans := n + 1, j := 0, sum := 0
定义一个双端队列dq
for 初始化 i := 0, 当 i < n, 更新 (i增加1), 执行：
如果 i > 0，则：
A[i] := A[i] + A[i - 1]
如果 A[i] >= K，则：
ans := ans 和 i + 1 的最小值
while (dq不为空且A[i] - dq的第一个元素 >= K)，执行：
ans := ans 和 i - dq的第一个元素的最小值
从dq中删除首元素
while (dq不为空且A[i] <= dq的最后一个元素A[dq])，执行：
从dq中删除尾元素
在dq的末尾插入i
返回 (如果ans与n + 1相同，则返回-1，否则返回ans)
让我们来看下面的实现，以便更好地理解：
示例
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
int shortestSubarray(vector<int> &A, int K) {
int n = A.size();
int ans = n + 1;
int j = 0;
int sum = 0;
deque<int> dq;
for (int i = 0; i < n; i++) {
if (i > 0)
A[i] += A[i - 1];
if (A[i] >= K) {
ans = min(ans, i + 1);
}
while (!dq.empty() && A[i] - A[dq.front()] >= K) {
ans = min(ans, i - dq.front());
dq.pop_front();
}
while (!dq.empty() && A[i] <= A[dq.back()])
dq.pop_back();
dq.push_back(i);
}
return ans == n + 1 ? -1 : ans;
}
};
main(){
Solution ob;
vector<int> v = {5,3,-2,2,1};
cout << (ob.shortestSubarray(v, 6));
}输入
{5,3,-2,2,1}, 6输出
2
更新于：2020年6月4日
380 次浏览
广告