Google 电面面经，一结束马上来发，求爆人品！

handsomecool 发表于 2015-7-8 09:08
第一题two pointers最简单吧，前后逐渐往中心靠近，两边各一个sum, 每次哪边小就哪边前进一位，直到两边见 ...

我刚开始也是想到这个。但是这个负数的情况是用不了的

赞，祝楼主拿到onsite

chenyy0527 发表于 2015-7-8 07:16
Two passes 是什么？
我是检测第一个element，然后遍历剩下的，每次对比一加一减就可以。都是O（n)

我想楼上说的Two passes可能是指：第一遍先得到所有的元素的和S；第二遍过的时候，如果某个元素A[i]的左边的和S[0, i-1]恰好等于总和(S-A[i])/2，则 i 就是所求的切分点（希望没有理解错题意）。

楼主说的这段：“检测第一个element，遍历剩下的，每次对比一加一减”我没太看懂。能否说得再详细一点？

补充内容 (2015-7-8 12:01):
原文中的A是A[ i ]. 万恶的斜体格式控制符……

maxnima 发表于 2015-7-8 10:35
赞，祝楼主拿到onsite

谢谢哦！！感动

stellari 发表于 2015-7-8 12:00
我想楼上说的Two passes可能是指：第一遍先得到所有的元素的和S；第二遍过的时候，如果某个元素A的左边的 ...

哦，可以的！
我的方法也是类似。就是对于A[0]检测所有两边的和（当然左边没东西），然后不等的话，检测下一个，左边的和是加上之前的元素，右边的和是减去右边的元素。（这是我所谓的一加一减）

然后一直对比直到找到

chenyy0527 发表于 2015-7-8 12:28
哦，可以的！
我的方法也是类似。就是对于A[0]检测所有两边的和（当然左边没东西），然后不等的话，检测 ...

明白了。不过这样的话不也是需要预先算出右边元素的和么？那最后其实也是two pass吧？

stellari 发表于 2015-7-8 12:33
明白了。不过这样的话不也是需要预先算出右边元素的和么？那最后其实也是two pass吧？

是的，所以很类似的。我一开始没理解two passes o.o

stellari 发表于 2015-7-8 12:33
明白了。不过这样的话不也是需要预先算出右边元素的和么？那最后其实也是two pass吧？

不过，你那个方法直接对比会有一点点问题，因为他要求【1，2，3】这种case不可以的，因为返回的坐标对应的元素要求两边都算，所以对比前要先把当前坐标再加一遍

chenyy0527 发表于 2015-7-8 12:37
不过，你那个方法直接对比会有一点点问题，因为他要求【1，2，3】这种case不可以的，因为返回的坐标对应 ...

我理解你的意思。但是不一定要“再加一遍”；“减一遍”也是可以的。因为“返回的坐标上的元素必须包含在左右两边”和“返回的元素必须不包含在任意一边”这两者无论是哪种情况，均不会影响本题的结果。我选择的是后者，即“把返回的元素从S中减掉”。所以，我说的那种方法也是不认可[1,2,3]的。

chenyy0527 发表于 2015-7-8 10:27
我刚开始也是想到这个。但是这个负数的情况是用不了的

还有负数哦，那改一下还是可以吧，依旧two pointers，两边哪边挪动的判定方式改一下：

这回不记左右两个sum了，两边加起来变一个sum, 但是把右边的正负号颠倒。 然后根据sum来看两边下一位取哪边的， 比如：   -5， -3， -1， -3， -7， -2

一开始sum = -5 + -(-2) = -3, 下一位两边一边是-3,一边是-（-7） = 7，那就右边挪。
现在sum = -3+7 = 4, 左边挪。
sum = 4 - 3 = 1
继续左边挪，sum = 1-1 = 0, 停止。