[leetcode][525] Contiguous Array

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

---

이진수 배열이 주어질 때, 0과 1의 개수가 같은 subarray의 최대 길이를 구하라.

---

부분합을 키로 하고 해당 부분합이 처음으로 나타난 위치(1이 시작점)를 value로 하는 map을 만든다.

0이 나오는 경우 합에 -1을 해주고 1이 나오는 경우 +1을 한다.

현재 탐색하고 있는 인덱스를 i라 하고 만약 이때까지 나온 부분합들 중 현재까지의 부분합(0~i)을 키로 하는 value가 있다면 i - value가 정답이 될 수 있는 경우이다.

예를 들어, 0011 이 있다면 subSum은 0 -1 -2 -1 0 이 된다. 가장 처음에 있는 0(시작)도 반드시 필요.

이 경우 정답이 될 수 있는 경우는 빨간색과, 파란색 인덱스들의 각 차이가 된다. 즉, 4, 2가 정답이 될 수 있고 이들 중 최대값인 4가 정답이 된다.

 

시간복잡도는 O(N). 

 

---

소스코드 : https://github.com/fpdjsns/Algorithm/blob/master/leetcode/medium/525.%20Contiguous%20Array.cpp