# 【LeetCode】 525. Contiguous Array

## Description
> Given a binary array, find the maximum length of a contiguous subarray with equal number of 0 and 1.
> Note: The length of the given binary array will not exceed 50,000.

> 給予一個二元陣列，找到最大長度的子陣列，其包含的0和1數量相同。
> 提示：給予的二元陣列最長不超過50000。

## Example:

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.

## Solution

* 這題蠻難的，想了很久才寫出來，時間還有夠慢XD
* 第一個重點是使用一變數sum，遇到`0`就減一，遇到`1`就加一。

class Solution {
public:
    int findMaxLength(vector<int>& nums) {
        int ans = 0;
        for(int j = 0; j < nums.size(); j++)
        {
            int sum = 0;
            int count = 0;
            for(int i = j; i < nums.size(); i++)
            {
                if(nums[i] == 0)
                    sum--;
                else if(nums[i] == 1)
                    sum++;

                count++;
                if(sum == 0)
                    ans = ans < count ? count : ans;
            }
        }
        return ans;
    }
};

* 上面是我寫出的第一個版本，就是把所有長度的總和都檢查一次。
* 複雜度為`O(n^2)`，吃到TLE。
---

* 改良加速版用了hash的概念，首先計算sum的時候，順便將sum取代掉原數字nums[i]。
* 假設今天nums為[1, 1, 0, 1, 0]，那麼新的nums就為[1, 2, 1, 2, 1]。
* 只要兩者數字相同，就代表該區間`0`和`1`是一樣多的！
* 因此我們用一個hash儲存每個sum值所在的位置。
* 如果hash沒有出現過該sum，就將它存入。
* 如我hash已經出現過了，那就計算長度。
* 複雜度為`O(n)`
* 如果還想要更快，必須使用`new`新增陣列取代掉`vector`等結構，以縮短allocate的時間。

### Code

class Solution {
public:
    int findMaxLength(vector<int>& nums) {
        int sum = 0;
        int ans = 0;
        unordered_map<int,int> hash;
        hash[0] = -1;
        int s = nums.size();
        
        for(int i = 0; i < s; i++)
        {
            if(nums[i] == 0)
                sum--;
            else if(nums[i] == 1)
                sum++;
            
            nums[i] = sum;
            if(hash.count(sum))
                ans = max(ans, i - hash[sum]);
            else
                hash[sum] = i;
        }
        
        return ans;
    }
};

###### tags: `LeetCode` `C++`