No525ContiguousArray

2019-11-08 02:25:30

字體：大中小

供稿：網(wǎng)友

當(dāng)場(chǎng)思路

開始沒注意Subarray, 以為是從頭開始數(shù), 就直接累計(jì)0和1的個(gè)數(shù)直到兩者相等返回位置就是長(zhǎng)度

后來(lái)思路

發(fā)現(xiàn)是subarray, 覺得可以用兩個(gè)數(shù)組zeros ones分別儲(chǔ)存0 1的累積數(shù)量再以最終數(shù)目小的那個(gè)數(shù)組為基準(zhǔn), 用zeros和ones的差來(lái)找到最長(zhǎng)的subarray 這個(gè)找最長(zhǎng)差的方法并沒有想到. 看看下面找最長(zhǎng)差的方法吧!

最優(yōu)方法 (別人的方法)

后來(lái)看了這個(gè)人的分享, 他就是我的想法的實(shí)用版本:https://discuss.leetcode.com/topic/79932/java-one-pass-o-n-solution-with-explanation他找最長(zhǎng)差的方法是用HashMap * HashMap用來(lái)儲(chǔ)存當(dāng)前Diff的最早的位置i * 后來(lái)的相同diff自動(dòng)比較位置相差長(zhǎng)度, 并讓結(jié)果一直保存最長(zhǎng)的 * 由于是最長(zhǎng)的一定開始最早, 所以相同diff只存最靠前的位置i * 適用于無(wú)規(guī)律數(shù)組尋找subarray自己寫的時(shí)候有bug, Failed Case: [0,1] 這個(gè)方法的diff[]長(zhǎng)度為nums.length+ 1 因?yàn)橐?,0放進(jìn)TreeMap, 表明開始的時(shí)候兩者數(shù)目相等

下一篇：Codeforces Round #398(Div. 2)B. The Queue【貪心+謹(jǐn)慎】這題好尼瑪強(qiáng)勁