C ++中的连续数组

  • Z时代
  • 2024-01-10
  • 分类：综合

假设我们有一个二进制数组，我们必须找到一个等于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

以上是 C ++中的连续数组 的全部内容， 来源链接： utcz.com/z/321710.html

回到顶部