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

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

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

cumulative(누적) sum different 개념을 활용한다. 앞의 문제 응용 :)

class Solution {
public:
	int findMaxLength(vector<int>& nums) {
		std::unordered_map<int, vector<int>> umap;
		umap[0].emplace_back(-1);
		int max = 0;
		int sum = 0;

		for (int i = 0; i < nums.size(); ++i)
		{			
			sum = sum + (nums[i] == 0 ? -1 : 1);
			nums[i] = sum;
			umap[sum].emplace_back(i);
			int diff = i - umap[sum][0];
			max = std::max(max, diff);
		}

		return max;
	}
};

Runtime: 140 ms, faster than 73.62% of C++ online submissions for Contiguous Array.

Memory Usage: 102.4 MB, less than 5.11% of C++ online submissions for Contiguous Array.