我的天展哭。。椎麦。
這道題我連最簡(jiǎn)單的暴力O(n^2)都沒(méi)想出來(lái)宰僧。 感覺(jué)有一種第一次就想追求optimal的solution， 暴力法的double loop想都沒(méi)去想观挎。 感覺(jué)兩個(gè)For loop 表示subarray的方法在我腦袋里仿佛完全不存在一樣撒桨。。键兜。
這個(gè)O(N)的算法就非撤锢啵恐怖了。普气。谜疤。
先用一個(gè)count 變量來(lái)儲(chǔ)存 1's 和0's 抵消后的值，比如0就代表0s 和1s一樣多现诀。用HashMap 記錄count的值夷磕，key為index。我花了不少時(shí)間才理解這個(gè)玩意的意思仔沿。
假設(shè)是同樣的count, 比如count =0. 可能是0011, 也可能是00001111 但是后者明顯更長(zhǎng)一點(diǎn)坐桩。由于我們之前見(jiàn)過(guò)0011， 把count =0 存在hashmap里了封锉。這次又遇到一個(gè)00001111, count =0的绵跷，我們可以用i - map.get(count)的key的值膘螟，也就是當(dāng)前index-上一次index， 來(lái)知道這個(gè)continous array的長(zhǎng)度碾局， 然后和maxLen做比較荆残。
疑問(wèn)：因?yàn)槲覀冎幌胫纄qual number? of 0's 和1's的 array長(zhǎng)度，那為什么map還要put count不等于0的時(shí)候净当？這是因?yàn)?如果從點(diǎn)i 到點(diǎn)i+n内斯， count的數(shù)量回到了一個(gè)水平，那就代表這一段內(nèi)總的0像啼，和1是一樣多的俘闯。這樣抵消之后才會(huì)使得count數(shù)量不變。所以i-map.get(count) 還是能告訴我們這段0,1數(shù)量一樣多的subarray的長(zhǎng)度
