525. Contiguous Array

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

1. Use brute force:

//Time Limit Exceeded
class Solution {
public:
    int findMaxLength(vector<int>& nums) {
        if(nums.size() == 0) return 0;
        int zero_count = 0, one_count = 0;
        for(int i = 0; i < nums.size(); i++){
            if(nums[i] == 0) zero_count++;
            else if(nums[i] == 1) one_count++;
        }
        int diff = one_count - zero_count;
        int result = 0;
        findMaxLength(nums, diff, result, 0, nums.size()-1);
        return result;
    }
private: 
    void findMaxLength(vector<int>& nums, int diff, int& result, int l, int r) {
        if(r - l < 1) return;
        //cout << l << " " << r << " " << diff << endl;
        if(diff == 0){
            result = max(result, r - l + 1);
            return;
        } else {
            if(nums[l] == 0)
                findMaxLength(nums, diff + 1, result, l + 1, r);
            else
                findMaxLength(nums, diff - 1, result, l + 1, r);
            if(nums[r] == 0)
                findMaxLength(nums, diff + 1, result, l, r - 1);
            else
                findMaxLength(nums, diff - 1, result, l, r - 1);
        }
    }
};

2. Use hashmap:

//300 ms    83.1 MB
class Solution {
public:
    int findMaxLength(vector<int>& nums) {
        if(nums.size() <= 1) return 0;
        unordered_map<int, int> map;
        //important
        map[0] = -1;
        int result = 0, count = 0;
        for(int i=0; i<nums.size(); i++){
            if(nums[i] == 0)
                count--;
            else
                count++;
            if(map.find(count) != map.end())
                result = max(result, i - map[count]);
            else
                map[count] = i;
        }
        return result;
    }
};