2020年4月13日 星期一

Leetcode題解 Python:四月挑戰DAY13 Contiguous Array

這題有難度,礙於我現在的時間管理策略,若沒能在時間內想到解法,就去找別人的理念講解,然後自己突破。參考

給一串數列,只有 0, 1,回傳 0 與 1 數量相等的子串列的最大長度。

0 與 1 數量相等,第一直覺就是要想到如何計數。如果不帶技巧,暴力解法需要 O(n**3) 時間解決。

如果要減少時間,那麼「用空間換取時間」的想法就可以派上用場,那麼空間要記錄些甚麼呢?

如果一個子串內的 0, 1 數量相等,總和會是長度的一半。也許派得上用場。(但沒有用)

先假設個 000111 ,若走到[2],0會是 3 個,走到[4],遇到 1 才會出現第一個合格長度 2。再遇到 1 變成長度 4,再遇到 1 變成長度 6。

由於 0、1 一定要都出現才會有長度,出現整排1跟0都不會出現合法長度,因此跟 0 與 1 數量差相關,數量差可以為 0,為 1,為 -1,這裡先繼續探索「數量差」是否能用。

0、1數量差為0,第一次出現在位置[-1],也就是起始值。下次 數量差0 出現在位置[5],因此 5 - (-1) = 6。數量差看起來是有用的。

若第一次紀錄後出現同樣的數量差,其中一定出現成對的 0、1。長度多少,因為只需要取最大長度,因此只要保留第一次出現的位置即可。

於是空間拿去紀錄各 0、1數量差 的出現位置。

回頭看 000111 走到 [3] 的時候,此時 0與1數量差 為2,上次出現 2 的位置為[1],長度為 3 - 1 = 2。
class Solution:
    def findMaxLength(self, nums: List[int]) -> int:
        memo = {0:-1} # 在 -1 位置,數量差一定為0
        counter0 = 0
        maxLength = 0
        for i in range(len(nums)):
            if nums[i] == 0: counter0 += 1
            else: counter0 -= 1                
            if counter0 not in memo:
                memo[counter0] = i
            else:
                maxLength = max(maxLength, i - memo[counter0])
        
        return maxLength