Given a binary array, find the maximum length of a contiguous subarray with equal number of 0 and 1.
Example 1:
Input: [0,1] Output: 2 Explanation: [0, 1] is the longest contiguous subarray with equal number of 0 and 1.
Example 2:
Input: [0,1,0] Output: 2 Explanation: [0, 1] (or [1, 0]) is a longest contiguous subarray with equal number of 0 and 1.
Note: The length of the given binary array will not exceed 50,000.
A:
每个位置,计算 count 1 - count0 的差, 并且存入一个map中。 然后每次找之前diff相同的。
class Solution { public: int findMaxLength(vector<int>& nums) { int n = nums.size(); unordered_map<int, int> M; M[0]=-1; int res = 0; int diff = 0; // count of 1 - count of 0 for(int i =0;i<n; i++){ diff += nums[i]==1?1:-1; auto iter= M.find(diff); if( iter != M.end()){ res = max(res, i - iter->second); }else{ M[diff] = i; } } return res; } };
No comments:
Post a Comment