525. Contiguous Array

525. Contiguous Array

題目給定一個陣列，陣列內有 0 和 1 兩種元素，要求最長的子陣列其內包含相同數量的 0 與 1 。

這個題目可以用暴力法解，透過窮舉出所有的子陣列就可以找到答案，但是當然這個題目有著更優的解法，不過我覺得這題是屬於有寫過才有機會可以寫得出來的題目。

第一個難點是要先知道怎麼把題目給的條件做一個轉換，在這個題目中，如果把 0 用作 -1 來參考的話，這個題目就可以用另一個方式來表達，也就變成找到最長的子陣列，而這個子陣列的總和會為 0 （因為此時 -1 和 1 一樣多）。

第二個難點是如何巧妙的避開窮舉？在上面的條件中，我們知道這個目標子陣列的總和會是零，那要怎麼知道這個情況呢？就是把每個位置的的元素一直相加，但這樣看起來還是像是窮舉，要怎麼巧妙的避開窮舉呢？既然我們都知道了在每個位置上包含所有之前元素的總和的值，這時候可以思考這個問題，如果我在位置 y 得到了總和為 2 ，那是不是我只要找到在「之前」的某個位置上其總和為 -2 的的情況，我就可以組合起來變成總和為零？

class Solution:
    def findMaxLength(self, nums: List[int]) -> int:
        n = len(nums)
        preSum = [0] * (n + 1)

        for i in range(n):
            preSum[i + 1] = preSum[i] + (-1 if nums[i] == 0 else 1)
        
        vToi = defaultdict(int)
        res = 0
        for i in range(n + 1):
            if preSum[i] not in vToi:
                vToi[preSum[i]] = i
            else:
                res = max(res, i - vToi[preSum[i]])

        return res