leetcode 525) Contiguous Array

LV. Medium 🧐

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

Contiguous Array - LeetCode

 

문제

Given a binary array nums, return the maximum length of a contiguous subarray with an equal number of 0 and 1.

 

Example 1:

Input: nums = [0,1]
Output: 2
Explanation: [0, 1] is the longest contiguous subarray with an equal number of 0 and 1.

Example 2:

Input: nums = [0,1,0]
Output: 2
Explanation: [0, 1] (or [1, 0]) is a longest contiguous subarray with equal number of 0 and 1.

 

Constraints:

• 1 <= nums.length <= 10^5
• nums[i] is either 0 or 1.

 

문제 해결법

map를 이용해서 간단히 해결할 수 있다.

map<int : count, int : index>

 

 0, 1, 2, 3, 4, 5, 6, 7, 8
[0, 1, 0, 0, 0, 0, 1, 1, 0]

위와 같은 배열이 있다고 하자.

count가 0을 map에서 찾고 계산할 수 있게 처음에 (count : 0, index : -1)로 map 넣어준다.

(index를 왜 -1로 넣었냐면 마이너스는 이상 이하의 값을 찾아주지 않고 이상 미만의 값을 찾아주기 때문!)

0일 때는 count값을 -1, 1일 때는 count의 값을 +1 해준다.

count 값이 map 안에 있을 때 maxlen의 값과 i - map[count]의 값과 비교해 더 큰 값을 maxlen으로 저장한다.

 

왜 i - map[count]로 배열의 길이를 찾는 걸까?

위의 예제를 코드로 돌렸다고 생각하면 map 안의 내용은 밑의 내용과 같다.

count, index
{ 0, -1 }
{ -1, 0 }
{ -2, 3 }
{ -3, 4 }
{ -4, 5 }

지금 현 인덱스가 7이라고 가정했을 때, count는 -2이다.

map에서 count -2인 인덱스는 3이다.

실제 배열을 확인하면 인덱스 4 ~ 7 범위로 하나의 contiguous subarray을 만들 수 있다.

 

count가 맵에 있다는 것은 0이나 1만 계속 있는 것이 아닌, 그 0이나 1을 짝지을 수 있는 다른 수가 있다는 것이기에 위와 같은 방식으로 계산할 수 있는 것이다.

 

해결 코드

class Solution {
public:
	int findMaxLength(vector<int>& nums) {
		int ans = 0;
		int count = 0;
		unordered_map<int, int> m;

		// count, index
		m.insert({0, -1});
		for (int i = 0; i < nums.size(); ++i) {
			count += nums[i] == 1 ? 1 : -1;
			if (m.find(count) == m.end())
				m.insert({count, i});
			else
				ans = max(ans, i - m[count]);
		}
		return ans;
	}
};