必考Contiguous Array [Map记录index]!

我的天。。。

这道题我连最简单的暴力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的长度

最后编辑于
©著作权归作者所有,转载或内容合作请联系作者
【社区内容提示】社区部分内容疑似由AI辅助生成,浏览时请结合常识与多方信息审慎甄别。
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

相关阅读更多精彩内容

  • 背景 一年多以前我在知乎上答了有关LeetCode的问题, 分享了一些自己做题目的经验。 张土汪:刷leetcod...
    土汪阅读 14,357评论 0 33
  • 1. Java基础部分 基础部分的顺序:基本语法,类相关的语法,内部类的语法,继承相关的语法,异常的语法,线程的语...
    子非鱼_t_阅读 33,392评论 18 399
  • java笔记第一天 == 和 equals ==比较的比较的是两个变量的值是否相等,对于引用型变量表示的是两个变量...
    jmychou阅读 5,433评论 0 3
  • 秋日阳光正好,俯拾午间石板,一阵温热,如许久前的一次回眸,一声浅笑。这感觉,如入旧日故里。 我站在石阶之上,默想伽...
    滢滢小镇阅读 1,796评论 0 0
  • 这篇文章来得晚了一些。 2016年对于我来说,是一个完整的独立年。从2015年底结束阿里巴巴的实习后,我就决定用这...
    符要疯阅读 2,713评论 5 4

友情链接更多精彩内容