facebook 2/6 onsite

find longest subarray

LZ这个题思路是啥，我想的是，先计算总和，然后用HashMap<Integer, ArrayList<Integer>>存，Key是数的值，ArrayList是index，然后遍历HashMap算每个Key的最大差值

比如

4 2 -2 -2 1 1 1 1 1 -1 -1 -1 -1
计算总和就是
4 6 4 2 3 4 5 6 5 4 3 2
然后存遍历一遍存到HashMap里面
<4, [0, 2, 5, 9]>
...
<2 [3, 11]>
...

类似这样，然后遍历HashMap算每个ArrayList的最大值减最小值，然后取最大

虽然时间复杂度是O(n)但是总感觉很冗余……求思路

sanguine 发表于 2015-3-29 09:52
LZ这个题思路是啥，我想的是，先计算总和，然后用HashMap存，Key是数的值，ArrayList是index，然后遍历 ...

一开始我也大概是这样，用了2d array，最后发现用map就好，一开始push (0,-1)，然后每次都看sum有没有在map里，有的话输出i- map.get(sum) 不然放进 (sum,i)

babysor 发表于 2015-3-31 07:19
一开始我也大概是这样，用了2d array，最后发现用map就好，一开始push (0,-1)，然后每次都看sum有没有在m ...

楼主我想问下这个subarray是连续的吗？

sanguine 发表于 2015-3-29 09:52
LZ这个题思路是啥，我想的是，先计算总和，然后用HashMap存，Key是数的值，ArrayList是index，然后遍历 ...

Hi 你好，我想问下你的算法结果是连续的subarray么？ 比如我有4 2 1 -2 的话怎么做呢

请问谁能解释一下这题的内容？

“3. 美国人听说我做题多，总是出一些怪题，find longest subarray 等于0 还要O（n）话leetcode那道find max retangle in boolean 2d array真是有趣啊，面试的话15分钟至少讲清楚演示清楚。.”

majiamajia 发表于 2015-10-7 05:25
请问谁能解释一下这题的内容？

“3. 美国人听说我做题多，总是出一些怪题，find longest subarray 等于0 ...

应该就是给你一个array， 找出其中最长的subarray，这个subarray所有的数字加起来是0. 我觉得要是是连续的话还好做点，要是不是连续的话感觉比较困难啊

colfighter 发表于 2015-10-7 05:27
应该就是给你一个array， 找出其中最长的subarray，这个subarray所有的数字加起来是0. 我觉得要是是连续 ...

是连续的哈。主要就是要推算过程，很容易发现一个map的精简解法

babysor 发表于 2015-10-7 08:08
是连续的哈。主要就是要推算过程，很容易发现一个map的精简解法

谢谢您我想想

babysor 发表于 2015-10-7 08:08
是连续的哈。主要就是要推算过程，很容易发现一个map的精简解法

多谢lz回复！恩是的，我之前在做另一道题，是一个array里面找出连续的subarray使之和为target，也是用的map思想，感觉可以用在这题。
题外话，如果可以不是连续的话lz有好想法吗？谢谢

babysor 发表于 2015-3-31 07:19
一开始我也大概是这样，用了2d array，最后发现用map就好，一开始push (0,-1)，然后每次都看sum有没有在m ...

似乎终于明白LZ说的算法，每次记录从开头到现在的SUM，然后CHECK一下SUM-TARGET在不在MAP里面，如果有输出来比较MAX LEN。另外如果SUM不在MAP里面，我们需要MAP.PUT(SUM, i),由于只用求最大的LEN， 我们不需要重复更新DUPLICATE的SUM。另外楼主一开始放（0， -1）也是很机智