###### tags: `Leetcode` `medium` `array` `hash` `prefix sum` `python` `c++`

# 525. Contiguous Array

## [題目連結:] https://leetcode.com/problems/contiguous-array/

## 題目:
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.

## 解題想法:
* 此題為給一只有0、1構成的數組，求其中最長的連續子數組長度(其中0、1個數相等)
* 解題技巧:
* **用計數器，linear遍歷計算1與0的數量差距: O(n)**
* **則當某兩個位置紀錄的差值為相同值，表示該兩位置的距離之間的1與0數量相等**
* trace示意圖

    nums=[1,1,0,1,1,0,1,0,0,1]
    遇1:+1 
    遇0:-1
    pos         0   1   2   3   4   5   6   7   8   9
    ex:         1   1   0   1   1   0   1   0   0   1
    count 0    '1'  2   1   2   3   2   3   2  '1'  2
    所以值為:   (pos)8-(pos)0=8
    即: 從頭到0的位置，1比0多1個; 從頭到8的位置，1比0多1個
    表示: 位置0~位置8，之間的1與0數量一致

* 因為差值要距離越遠越好，所以希望是越遠的減越近的位置
* 可以利用字典紀錄差值第一次出現的位置
* dic=collections.defaultdict(int)
* key: 1與0的差值
* value: 當前位置
* 需設立初始值
* dic[0]=-1，差值0的位置為-1
* 理由: 因為若未設立初值，則若遇到nums=[0,1]此case，count=-1,0，沒有相等的比照值無法計算判別

## Python:

from collections import defaultdict
class Solution(object):
    def findMaxLength(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        #技巧!!用個計數器 Linear遍歷計算1與0的數量差距 O(n)
        #當某兩個位置分別同為相同值 代表其中的1與0數量相等
        dic=defaultdict(int) #key為1與0的差值 value為pos
        dic[0]=-1 #需設初始值 以免遇到nums=[0,1] 若沒給初始，則count=-1,0 會無法辨別
        res=0
        count=0
        for pos,val in enumerate(nums):
            count+=1 if val==1 else -1
            if count in dic:
                res=max(res,pos-dic[count])
            else:
                dic[count]=pos
        return res
        
if __name__ == '__main__':
    result=Solution()
    nums=[1,1,0,1,1,0,1,0,0,1]
    ans=result.findMaxLength(nums)
    print(ans)

## C++:

class Solution {
public:
    int findMaxLength(vector<int>& nums) {
        unordered_map<int,int> dic;
        dic[0]=-1;
        //key: diff in 1 and 0
        //val: current position
        int res=0, count=0, n=nums.size();
        for (int pos=0; pos<n; ++pos){
            (nums[pos]==1)? count+=1: count-=1;
            if (dic.find(count)!=dic.end())
                res=max(res, pos-dic[count]);
            else
                dic[count]=pos;
        }
        return res;
    }
};