資料結構
網路
關係資料庫管理系統(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 次瀏覽
廣告