c*********t
发帖数: 2921 | 1 看到最近有人问4sum的问题，
可是我想如果能对2sum ,3sum的问题弄透了，各种方法都研究一下，4sum应该就是一个
扩展，对吧。
我们能不能先列一下可以解决2sum的所有方法？假设数组中有重复的数。
有种方法是用hashtable,可是我发现有个问题，
比如给定数组 [ 1 2 3 4 5 6 7 8 9],求出之和为 10 (target)的两个数，
用hashtable,我们可以得到
1 9
2 8
3 7
4 6
5 5 <<<<<<<这里好像不对了，因为数组里只有一个5,这个问题该如何处理？
6 4
7 3
8 2
9 1
另外就是得出的组合有重复的，象 1 9, 其实和 9 1 是一回事，该怎么办？
还有哪些常用的方法来解决2sum问题的？
谢谢！ |
|
y*d
发帖数: 2226 | 2 3sum的思路可以用于2sum，但是用在2sum上就是脱了裤子放屁
因为2sum有1万种解法都是nlogn的
4sum也许有更神奇的解法
我知道的就是在3sum基础上再乘n |
|
s*******m
发帖数: 228 | 3 2Sum, 3Sum, 4Sum
稍微有点变化的是, array中数字是0-10, target也是0-10的. 要求输出在数组中最先
遇到的
满足条件的
pair(2sum)
triplet(3sum)
4个数字组(4sum) |
|
t*********n
发帖数: 89 | 4 2sum,如果用hash table的话，循环中每一次查元素都只在已有的hash table 查，比如
1 -> 此时 hash table为空，则无结果
2 -> 此时 hash table 里有仅有1， 无结果
....
9 -> 此时 hash table 里有{1，2，3，..8},查到1，成立
对于duplicate,我的想法是在hash_table的value以一个bool来表示是否已经用过，即
hash_table myhash。比如数组为{5，5，5}，目标是10
5-> 此时hash table为空，无结果
5-> 此时hash table里面有5，标记myhash[5] = false;
5 -> 此时hash table里面虽然有5，但是myhash[5] = false,则不成立。
请问下大家有没有更巧的方法？ |
|
d*k
发帖数: 207 | 5 之前的帖子有个FB的面试题，三个数组A,B,C，nlogn的时间下找到A中的a, B中的b，C
中的c，使得a+b+c=0。有人跟帖提到2sum可以logn，弱问下怎么做。 |
|
s****9
发帖数: 22 | 6 2sum目测可以lg n啊
lgn + 1/2 lgn + 1/4 lgn ... |
|
c*******y
发帖数: 570 | 7 还需要2sum？不应该是会for循环打印1到10就够了吗 |
|
s*******m
发帖数: 52 | 8 一般来说2sum 直接排序，然后2pointer, nlogn 的时间
或者是hashmap， O(n) 的时间
题目变成这样， 比如我给 （2，2，2）， target = 4，
我要输出所有可能的index， 也就是 {0，1}， {0，2} ， {1，2}
想了下，是用HashMap 存一个index list的话。遍历每个元素是O(N)，找到解了，打印
list中每个元素要O(n), 一共是n平方。
如果用2 pointer，似乎也没办法O(n)
各位大神有没有啥想法？ |
|
u**r
发帖数: 663 | 9 n个数有n*(n-1)/2个2sum,把这些2sum记录在哈希表中,然后对每一个(target-2sum)值,
查哈希表看(target-2sum)是否在前面计算的2sum集合中,是的话就找到了要求的4sum.
时间空间复杂度都是O(n^2). |
|
u**r
发帖数: 663 | 10 n个数有n*(n-1)/2个2sum,把这些2sum记录在哈希表中,然后对每一个(target-2sum)值,
查哈希表看(target-2sum)是否在前面计算的2sum集合中,是的话就找到了要求的4sum.
时间空间复杂度都是O(n^2). |
|
d******l
发帖数: 175 | 11 感谢回复！我现在的解法就是像你说的，把原来的数组取出一个数来做2sum（2sum使用
hashmap来做的）。我没有一开始就排序，而是没得到一个2sum以后，把当前拿出来的
那个元素跟2sum的结果并在一起得到resArrayList。再对resArrayList排序。由于
resArrayList只包含3个元素，所以应该对整体复杂度没有什么影响。然后再通过判断
这个resArrayList是不是已经存在于最后的解resList里面，不存在的话，就resList.
add(resArrayList)。我现在还没有明白解法里面是哪儿导致复杂度太高。。。可否请
你再帮忙分析一下？
再次感谢发的链接。 |
|
u**r
发帖数: 663 | 12 有重复的话可以在哈希表里头记录重复次数阿，比如你给的例子中2sum=9有3种情况,那
么hash(9)=3就可以了,每次判断的时候可以这么做,
k=9; //for this 2sum, find if any other 2sum pairs with it to get the target
hash[k]--;
if(hash[target-k] > 0) return true; // found it;
hash [k]++; |
|
u**r
发帖数: 663 | 13 有重复的话可以在哈希表里头记录重复次数阿，比如你给的例子中2sum=9有3种情况,那
么hash(9)=3就可以了,每次判断的时候可以这么做,
k=9; //for this 2sum, find if any other 2sum pairs with it to get the target
hash[k]--;
if(hash[target-k] > 0) return true; // found it;
hash [k]++; |
|
s********s
发帖数: 49 | 14 代码好长啊。。。其实有了2sum,3sum的做法很直观吧：先取出一个数，那么只要在剩
下的数字里面找到两个数字使得他们的和等于(target – 那个取出的数)就可以了吧。
所以3sum就退化成了2sum, 取出一个数字，这样的数字有N个，所以3sum的算法复杂度
就是O(N^2 )。
注意你排序只需要排一次，后面的工作都是取出一个数字，然后找剩下的两个数字，找
两个数字是2sum用头尾指针线性扫，这里很容易错误的将复杂度算成O(N^2 log N)，这
个是不对的。
可以参考这个总结 http://tech-wonderland.net/blog/summary-of-ksum-problems.html |
|
s********o
发帖数: 3783 | 15 面试遇到的题目有非常多都是leetcode原题
比如我上面提到的2sum，跟leetcode一模一样
下面是一些题，不分先后，不分公司，全混在一起说
1，leetcode 2sum，用O(nlogn)和O(n)怎么做
2，leetcode 2sum，如果是小于不是等于怎么做，3sum怎么做，小于x怎么做
4sum怎么做，小于x怎么做，只输出符合条件（小于x）的总个数但是不需要输出具体数
怎么做，不但输出总个数还要输出具体答案怎么做，k sum 小于x怎么做，
k sum有没有多项式解？证明之
3，一个城市的地图（mxn矩阵），求从左上到右下一共有多少种可能的路线（只能向右
和向下）。先用程序写（利用通项公式递推），然后让我在白板上写close form公式
其实close form非常非常简单，只不过我没见过这道题，当场没有看出来。但是我硬挺
着从通项公式开始用矩阵分解去求解close form，最后在面试官的一点帮助下还是写出
来了公式，最后面试官表示我的数学基本功非常令他吃惊。（我心里想好歹也是学过几
门数学课的）。。。
4，还是数学题，求k个数的最大公约数。其实就几行代码，辗转相... 阅读全帖 |
|
s********o
发帖数: 3783 | 16 面试遇到的题目有非常多都是leetcode原题
比如我上面提到的2sum，跟leetcode一模一样，一模一样的我就不说了。
下面是一些题，不分先后，不分公司，全混在一起说
1，leetcode 2sum，用O(nlogn)和O(n)怎么做
2，leetcode 2sum，如果是小于不是等于怎么做，3sum怎么做，小于x怎么做
4sum怎么做，小于x怎么做，只输出符合条件（小于x）的总个数但是不需要输出具体数
怎么做，不但输出总个数还要输出具体答案怎么做，k sum 小于x怎么做，
k sum有没有多项式解？证明之
3，一个城市的地图（mxn矩阵），求从左上到右下一共有多少种可能的路线（只能向右
和向下）。先用程序写（利用通项公式递推），然后让我在白板上写close form公式
其实close form非常非常简单，只不过我没见过这道题，当场没有看出来。但是我硬挺
着从通项公式开始用矩阵分解去求解close form，最后在面试官的一点帮助下还是写出
来了公式，最后面试官表示我的数学基本功非常令他吃惊。（我心里想好歹也是学过几
门数学课的）。。。
4，还是数学题，求k个数的最大公约数... 阅读全帖 |
|
发帖数: 1 | 17 某ID：
明明是某些国男不断地散步谣言，说女生进flag面试超简单,
甚至有的都已经说成连2sum写不顺的女生都能进。然后
国女亲自去面试，发现是谎话，所以到网上来说没见到照顾。
让我直接笑出了声。
原来现在某些女生已经到了“自己遇不到2sum就是没见到照顾”的境界了吗？她们脑子
里只有两种题，一种是“2sum”，一种是她们不会做的题。 |
|
T*******e
发帖数: 4928 | 18 你真能歪解。人家女生说得是什么只要是个女生
就受照顾，差到面试2sum写不顺的都能进flag的
传言不真实，根本就没说面试官没出2sum吧。
而且谷歌很少出leetcode 原题。这大家都知道吧。
我面试的时候就没见到一道练过的leetcode的题。
连2sum的变形都没有。 |
|
w***t
发帖数: 1474 | 19 万一2sum和target-2sum这两个sum包含同一个元素咋办。
sum1 = a + b;
sum2 = a + c;
target = a + a + b + c; 这样是错的把
值, |
|
w***t
发帖数: 1474 | 20 万一2sum和target-2sum这两个sum包含同一个元素咋办。
sum1 = a + b;
sum2 = a + c;
target = a + a + b + c; 这样是错的把
值, |
|
h********u
发帖数: 134 | 21 应该可以不用排序，省掉这些时间
对于每个number，求他的-number可以直接用2sum来做，2sum就是o(n) |
|
D**********d
发帖数: 849 | 22 想到一个 O(n^3) 的解法：
1. sort on x axis -- O(nlg(n)) x1 <= .... <= xn
2. for each pair (n1,n4) check d(n1,n4) == sqrt(2)L,
if yes, check 2sum problem on x: s.t. x2+x3 = x1 + x4
if yes, check d(n2,n3) == sqrt(2)L,
if yes, output (x1,x2,x3,x4)
n^2 pairs * 2sum = O(n^3)
|
|
K*********n
发帖数: 2852 | 23 这个2sum用得挺好，貌似这样可以吧……
不过每一个pair可能能形成两个正方形，所以2sum最后一步，找到n2和n3后，不能quit
，可能还有一对儿n2和n3. |
|
f*********d
发帖数: 140 | 24 NDA滚犊子:)
12:45 HR美女带上楼
////////////////////////
1
////////////////////////
白人年轻哥们比较牛，感觉他反应很快。。但很nice
来了三年多了。。。
单词路径查找问题。。。
刚开始做得不顺利，
提了建立图
再提了bfs
bfs + hash
写了个递归解的code
////////////////////////
2
////////////////////////
刚来的白人本科毕业生
题目出得不难
bst hash比较
相似字符串analog
先用排序方法
再用hash方法
都写了code
////////////////////////
3
////////////////////////
白人大哥30多岁，来7年半了
讲project
排序复杂度
问题等价于 找两个整数，使得和最解接近目标解，但不能超过
会2sum problem，就会这个做问题
平方解
nlogn解
O(n)解 失败， 2sum可以用hash，这个貌似不行，他同意了
写了nlogn的代码
////////////////////////
... 阅读全帖 |
|
d*******8
发帖数: 30 | 25 发现我说错了，应该是o(n2) 。我是想说从2sum变形过来的，2sum是O(nlogn). 不过排
序是o(nlogn) , 找只要o(n)...
看来接到邮件混乱了 |
|
r**********o
发帖数: 50 | 26 题目是给出所有milestone pair的distance了么？ 还是只给部分的？
如果是给出所有的，那么排序找出最大值，之后做2Sum，2Sum的合格对，排序，算出结
果，为什么不行呢？ |
|
z***m
发帖数: 1602 | 27 我python code是这样写的:
def TwoSum_HashTable(lst, target):
hashTable = dict()
for x in lst:
hashTable[x] = True
for x in lst:
y = target-x
if y in hashTable and x != y:
return (x, y)
return None
lines = open('2sum.txt').read().splitlines()
data = map(lambda x: int(x), lines)
count = 0
for t in range(-10000, 10000+1):
if(TwoSum_HashTable(data, t)):
count +=1 # # find if there exists such pair
print count
-----... 阅读全帖 |
|
s*******s
发帖数: 1031 | 28 找工作结束了，从版上学到了很多东西，总结一下我的经历回报版上，希望大家都能拿
到心仪的offer。
本人纯DS男一枚，跟本上的牛人绝对没得比。总结一下我这几个月的申请经验。
先后面试了几家公司，拿到了A, MS 和 G 三家的面试。A家7月初面试结束后到现在对
我不管不问，不说拒也不说不拒，应该是默剧了。 M家是8月中oniste的，第二天出的
offer。一周后的周一面试的G家，因为有MS家的offer让我赶快答复，我就push G 家快
点出结果， G家当周的周五确认我拿到offer。
最后我选择了去G家，package很DS，跟版上牛人的没得比，就不拿出来献丑了。
先上面经。
A家：
先是2轮电面。然后参加了onsite，见到了6个人。
电面1: 老美白人
1. talk about a scenario during your works, when the manager did not
want to take your advice, but you try to finished it at your own time.
2. ... 阅读全帖 |
|
s*******s
发帖数: 1031 | 29 找工作结束了，从版上学到了很多东西，总结一下我的经历回报版上，希望大家都能拿
到心仪的offer。
本人纯DS男一枚，跟本上的牛人绝对没得比。总结一下我这几个月的申请经验。
先后面试了几家公司，拿到了A, MS 和 G 三家的面试。A家7月初面试结束后到现在对
我不管不问，不说拒也不说不拒，应该是默剧了。 M家是8月中oniste的，第二天出的
offer。一周后的周一面试的G家，因为有MS家的offer让我赶快答复，我就push G 家快
点出结果， G家当周的周五确认我拿到offer。
最后我选择了去G家，package很DS，跟版上牛人的没得比，就不拿出来献丑了。
先上面经。
A家：
先是2轮电面。然后参加了onsite，见到了6个人。
电面1: 老美白人
1. talk about a scenario during your works, when the manager did not
want to take your advice, but you try to finished it at your own time.
2. ... 阅读全帖 |
|
|
T*******e
发帖数: 4928 | 31 你说的是leetcode上的2sum。
只是在真正的面试中，2sum可能是让输出indices of all pairs sum to target.
or all pairs sum to target without dup in result并分析时空复杂度.不难，但 都
是有些要注意的细节，平时刷题的时候也得想想变形。
）.
containsKey( |
|
m****t
发帖数: 555 | 32 triplet那道题，简单的做法和3sum差不多。先排序，转化为2sum问题。对于每个a[i],
计算a[j], a[k] 的 2sum。 头尾 j,k 两二个指针往中间走，if a[j]+a[k]<=X-a[i]
，则count += k-j;最后输出count.
这样的时间复杂度是O(n^2). |
|
c*****m
发帖数: 271 | 33 2sum问题只能处理等于某数的情况吧，如1,2,7,8, 要求2sum<=9的，这里只有两个，而
不是3个
], |
|
l********g
发帖数: 372 | 34 对于k sum, k>=3的，都先用nlogn排序后进行上头说的那样的跳跃法子来进行两指针的
2sum，复杂度应该都是O(n^(k-1))。 2sum本身因为要O(n)了所以无序的大家一般不会
先sort。 |
|
C****t
发帖数: 53 | 35 N^2的问题。一个指针固定下来后，变成2sum问题。2sum有hash解法和非hash解法。 |
|
b*****X
发帖数: 22 | 36 赞一下上次面我的老中，电面刚开始上来语气挺凶的，我以为要被黑了，coding他掏出
2sum和permutation我就知道是自己人~feedback也是positive ... 可惜自己实
力不够后面死在老印手里了 ~ 自己还挺惭愧刚开始误会人家了
我要是有机会面试别人我也只考2sum和permutation |
|
x******0
发帖数: 178 | 37 作为前领英，如今的微软员工。看到满屏的骂领英，刚开始很气愤，后来就是感觉悲哀
了。
真的不是很明白为什么会有这么多讨厌L的人，看了一些帖子，无外乎就三个理由，烙
印多，小中多，面试不给老中放水。我在L两年了，也算不短了，就说说自己的看法。
烙印多：烙印的确不少，但也就是相对数量不少。L总共也就2000不到的码工，能有多
少烙印？我敢说在L里面老中烙印的比例绝对相当。是的，中高层的烙印相对多，但是
我也没看到多少打压老中员工的例子，至少不会比我以前待的公司里面老美压迫老中过
分。烙印抱团的确存在，烙印坐火箭升上去的的确多，但是老中们待的年限久了，也有
不少升到高层的。当然了，我承认，以后如果裁员，可能情况会恶劣一些。现在最多就
是升职慢。但是这种情况在别的公司真的没有？
小中多：小中大多都是cmu之类的学校master毕业，我接触过很多，感觉都是很不错的
年轻人。没有遇到多少板上人人抨击的用鼻孔看人的现象。再有就是，年轻人年少轻狂
一点没什么不好。我就后悔自己年轻的时候在职场唯唯诺诺，畏首畏尾，很没出息。
面试不给老中放水：地球人都知道，L面试有3点：有题库，每轮两个人，重视交流。我
两... 阅读全帖 |
|
c********t
发帖数: 5706 | 38 应该是 O(n^2 * m)吧 m is average duplicate 2sum number
1，2，3，4，5，6
target 14
要找出所有解，肯定要处理2sum的duplicate |
|
发帖数: 1 | 39 板上说的2sum从来都是开玩笑吧，fg至少4轮的onsite怎么可能有2sum写不利索最后拿
offer的。但是“有的人说女生面试题会简单，然后有的女生去了发现自己的题目不那
么简单，就觉得自己没收到优待，就来抱怨”这个呢？ |
|
|
i*****e
发帖数: 68 | 41 喜欢这个证明.能用简单工具解决问题最好.
如果把条件sum h_i =sum r_i =1 去掉,你这个办法实际上证明了
2sum r_i -sum h_i <= sum(r_i^2/h_i).
前面几位用C-S证明的是
(sum r_i)^2 /(sum h_i)<= sum(r_i^2/h_i).
由于2sum r_i -sum h_i <=(sum r_i)^2 /(sum h_i),所以C-S 实际上证明了一个更强
的不等式.总之,个有长处吧. |
|
m****d
发帖数: 331 | 42 P(W=j)=sum((m=0,1,...)(P(x=m,Y=m+j)+P(x=m+j,Y=m))=2sum((m=0,1,...)(P(x=m,Y=m
+j))
=2sum((m=0,1,...)(P(x=m)P(Y=m+j))
=2(1-p)^2*p^j*sum(m,p^2m)
correct?
p) |
|
d******e
发帖数: 7844 | 43 Sum(Xi-1)^2
=Sum(Xi^2) - 2Sum(Xi) + n
=Sum(Xi) - 2Sum(Xi) + n
=n-Sum(Xi)>0
高中数学啊... ... |
|
|
c*******a
发帖数: 1879 | 45 你可能就会2SUM这样的题目。
你把你刷的CODE贴上来看看， 让将军们给你 review一下。 |
|
Z**********g
发帖数: 14173 | 46 这几天天天的扯淡，过几天估计就忘了，赶紧发下。求转Jobhunting
大概两周前面的，西雅图，Hiring Event，就一上午，只有四轮，很快。不过8点就开
始，真心累死，西雅图还有3个小时时差，日了狗了。
第一轮，老印，算法，2Sum + Followup；因为LeetCode第一题，所以很简单就答出来
了。然后问了个reverse string，也很简单，然后是reverse string ii，没写完，说
了思路；
第二轮，白人，算法，就是给一个矩阵，从左上角走，右下角为终点，问有多少种走法
那道经典题，dp解决。Followup是如果有坑过不去怎么办，我说把那点的dp reset就可
以，没让写code。
第三轮，老中师兄，细节不暴露太多了，说不定他也看着我的帖子呢。估计他肯定照顾
我了。两道利特扣德，一道EZ一道谜底额穆。
第四轮，manager，老中，问的是简历、课程，让我讲一个课程的project做了什么，我
还是比较能吹的。
总体感觉不难。我本人改行出身，刷题的天资不错，最后一共做了大概270道LeetCode
题，考的题也基本上都是前300道。 |
|
|
|
|
Z**********g
发帖数: 14173 | 50 什么啊，2Sum的重复性在于，比如允许一个元素用两次，不允许一个元素用两次。
比如只有5，那input 10怎么办？
其次，如果有多个结果怎么办？要求都返回，怎么去重？
还有，如果不允许用HashTable怎么办？
总之，看似非常简单，其实snowday是不会的。 |
|
