[Leet] - 525. Contiguous Array [hash] - c++

mopevxw·2022년 2월 8일
0

LeetCode

목록 보기
19/21

https://leetcode.com/problems/contiguous-array/

c++ unordered_map 풀이

  1. unordered_map <sum:현재까지의 합, index:최초로 sum값의 index>
  2. 최초 시작은 <sum:0,index:-1>로 시작 0 만나면 sum-1 / 1 만나면 sum+1
  3. 같은 sum을 마주침 = 조건 성립 => 길이 비교 후 초기화
    sum을 마주치지 않는 경우 mp[sum] 새롭게 값 추가
class Solution {
public:
    int findMaxLength(vector<int>& nums) {
        unordered_map<int,int> mp;
        mp[0]=-1;
        int ans=0;
        int sum=0;
        for(int i=0;i<nums.size();i++)
        {
            
            sum += nums[i]==1? 1:-1;
            if(mp.find(sum)!=mp.end())
            {
                ans=max(ans, i-mp[sum]);
            }
            else
            {
                mp[sum]=i;
            }
        }
        
        return ans;
    }
};

0개의 댓글