10/23 gougou面经

修正：第二轮是问array里找subarray的最长长度，要和为0的subarray。sum最大就简单了。。不知道为什么写成了sum最大。。

谢谢楼主分享 请问第二题怎么解？

补充内容 (2017-11-13 04:25):
用hashmap算accumulated sum这样吗

quingogo 发表于 2017-11-13 04:24
谢谢楼主分享 请问第二题怎么解？

补充内容 (2017-11-13 04:25):

嗯嗯对的～

shenqi77 发表于 2017-11-12 06:25
差不多吧，有对应关系所以建个2d array，然后在之前发生过的true‘s的基础上看是否在新位置匹配到。

在想是不是recursion的做

quingogo 发表于 2017-11-13 04:24
谢谢楼主分享 请问第二题怎么解？

补充内容 (2017-11-13 04:25):

第二题应该是里抠 伍伞 吧。

用一个DP就可以O(n)了

yuyuyu0905 发表于 2017-11-13 10:08
第二题应该是里抠 伍伞 吧。

用一个DP就可以O(n)了

你看楼主后来加的描述信息 并不是伍伞 但好像有印象有见过类似的

quingogo 发表于 2017-11-13 11:55
你看楼主后来加的描述信息 并不是伍伞 但好像有印象有见过类似的

对的，不是五伞，要sum为0的最长子array

四轮三轮国人，只求有楼主这样的人品。

quingogo 发表于 2017-11-13 11:55
你看楼主后来加的描述信息 并不是伍伞 但好像有印象有见过类似的

哦哦不好意思~我还说这个题怎么画风不一样

quingogo 发表于 2017-11-13 11:55
你看楼主后来加的描述信息 并不是伍伞 但好像有印象有见过类似的

那感觉应该是hashmap存一下0到i的和。是0就返回index加1，不是0就在hashmap里找。找得到就返回差值，找不到就存index？

这样可以 average O(n)