假设我们有一个二进制数组,我们必须找到一个等于0和1的连续子数组的最大长度。因此,如果输入是[0,1,0],那么输出将是2,即[0, 1]或[1,0]是具有0和1相等数目的最大连续数组。
为了解决这个问题,我们将遵循以下步骤-
ret:= 0,n:= nums大小,sum:= 0
制作映射m,设置m [0]:=-1
对于0到nums大小范围内的i – 1
sum:= sum + 1,如果nums [i]为1,否则sum:= sum – 1
如果总和以m为单位,则ret:= ret和i – m [sum]的最大值,否则m [sum]:= i
返回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