C++の連続配列

バイナリ配列があるとすると、0と1の数が等しい連続したサブ配列の最大長を見つける必要があります。したがって、入力が[0,1,0]の場合、出力は[0、 1]または[1,0]は、0と1の数が等しい最大の連続配列です。

これを解決するには、次の手順に従います-

• ret：=0、n：=numsのサイズ、sum：=0
• マップmを作成し、m [0]を設定します：=-1
• 0からnumsのサイズまでの範囲のiの場合– 1
  • sum：=nums[i]が1の場合はsum+1、それ以外の場合はsum：=sum – 1
  • 合計が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