数据结构
网络
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+ 查看
广告