資料結構
網路
RDBMS
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化學
生物
數學
英語
經濟學
心理學
社會學
時尚研究
法律研究C++ 中的最小大小子陣列和
假設我們有一個包含 n 個元素和正整數 s 的陣列。我們需要找到一個連續子串的最小長度，其和大於或等於 s。如果沒有，則返回 0。因此，如果陣列類似於 [2,3,1,2,3,4] 且和為 7，則輸出將為 2。這是此案例中具有最小長度的子字串 [4,3]。
為解決此問題，我們將遵循以下步驟：
ans := 0，n := 陣列 A 的大小，j := 0 和 sum := 0
對於從 0 到 n-1 的 i
sum := sum + A[i]
當 sum – A[i] >= k 且 j <= 1 時
sum := sum – A[j]
將 j 增加 1
如果 sum >= k，則
如果 ans = 0 或 ans > (i – j + 1)，則 ans := (i – j + 1)
返回 ans
讓我們瞭解一下以下實現以便更好地理解：
示例
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
int minSubArrayLen(int K, vector<int>& A) {
int ans = 0;
int n = A.size();
int j = 0;
int sum = 0;
for(int i = 0; i < n; i++){
sum += A[i];
while(sum - A[j] >= K && j <= i){
sum -= A[j];
j++;
}
if(sum >= K){
if(ans == 0 || ans > (i - j + 1)) ans = (i - j + 1);
}
}
return ans;
}
};
main(){
vector<int> v = {2,3,1,2,4,3};
Solution ob;
cout << ((ob.minSubArrayLen(7,v)));
}輸入
7 [2,3,1,2,4,3]
輸出
2
更新於：2020 年 4 月 30 日
1K+ 檢視
廣告