我的天。。。
这道题我连最简单的暴力O(n^2)都没想出来。 感觉有一种第一次就想追求optimal的solution, 暴力法的double loop想都没去想。 感觉两个For loop 表示subarray的方法在我脑袋里仿佛完全不存在一样。。。
这个O(N)的算法就非常恐怖了。。。
先用一个count 变量来储存 1's 和0's 抵消后的值,比如0就代表0s 和1s一样多。用HashMap 记录count的值,key为index。我花了不少时间才理解这个玩意的意思。
假设是同样的count, 比如count =0. 可能是0011, 也可能是00001111 但是后者明显更长一点。由于我们之前见过0011, 把count =0 存在hashmap里了。这次又遇到一个00001111, count =0的,我们可以用i - map.get(count)的key的值,也就是当前index-上一次index, 来知道这个continous array的长度, 然后和maxLen做比较。
疑问:因为我们只想知道equal number� of 0's 和1's的 array长度,那为什么map还要put count不等于0的时候?这是因为 如果从点i 到点i+n, count的数量回到了一个水平,那就代表这一段内总的0,和1是一样多的。这样抵消之后才会使得count数量不变。所以i-map.get(count) 还是能告诉我们这段0,1数量一样多的subarray的长度