C++의 연속 배열

<시간/>

이진 배열이 있다고 가정하고 동일한 수의 0과 1을 가진 연속 하위 배열의 최대 길이를 찾아야 합니다. 따라서 입력이 [0,1,0]과 같으면 출력은 [0, 1] 또는 [1,0]은 0과 1의 개수가 동일한 가장 큰 연속 배열입니다.

이 문제를 해결하기 위해 다음 단계를 따릅니다. −

ret :=0, n :=숫자의 크기, 합계 :=0
지도 m 만들기, m[0] :=- 1로 설정
0에서 숫자 크기 – 1까지 범위에 있는 i의 경우
- sum :=sum + 1이면 nums[i]가 1이고 그렇지 않으면 sum :=sum – 1
- 합계가 m이면 ret :=ret의 최대값이고 i – m[sum]이고 그렇지 않으면 m[sum] :=i
반환

이해를 돕기 위해 다음 구현을 살펴보겠습니다. −

예

#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]