C++ 中的连续数组
c++server side programmingprogramming更新于 2024/9/27 23:58:00
假设我们有一个二进制数组，我们必须找到一个连续子数组的最大长度，其中 0 和 1 的数量相等。因此，如果输入为 [0,1,0]，则输出将为 2，因为 [0,1] 或 [1,0] 是 0 和 1 数量相等的最大连续数组。
为了解决这个问题，我们将遵循以下步骤 −
- ret := 0, n := size of nums, sum := 0
- 制作一个映射 m，设置 m[0] := - 1
- for i in range 0 to size of nums – 1
- 当 nums[i] 为 1 时，sum := sum + 1，否则 sum := sum – 1
- 如果 sum 在 m 中，则 ret := ret 和 i 的最大值 – m[sum]，否则 m[sum] := i
- return ret
让我们看看下面的实现以便更好地理解 −
示例
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
int findMaxLength(vector<int>& nums) {
int ret = 0;
int n = nums.size();
int sum = 0;
map <int, int> m;
m[0] = -1;
for(int i = 0; i < nums.size(); i++){
sum += nums[i] == 1 ? 1: -1;
if(m.count(sum)){
ret = max(ret, i - m[sum]);
}else m[sum] = i;
}
return ret;
}
};
main(){
vector<int> v = {0,1,0,0,1};
Solution ob;
cout << (ob.findMaxLength(v));
}
输入
[0,1,0,0,1]
输出
4
