H***e 发帖数: 476 | 1 1。 一个array,找两个数字使得和为0,简单,只要用一个hashtable就可以了, 只需
要走一遍, O(n) time O(n) space
2。 三个数字和为0, a+b+c = 0, 那么a+b+c = 0,那么 array当中必须有负数才行,
把正数和负数分开,分别放到两个hashtable中: 正hashtable和负hashtable.
a+b+c = 0, 组合只有可能 ++- or --+, 所以对 每个正hashtable的元素a,看有没有
两元素加起来为'-a';对 每个负hashtable的元素b,看有没有两元素加起来为'-b',如
果有,则为解。 O(n^2) time, O(n) space
3。 四个元素为0。这个是怎么有time O(n^2)的解的?space是多少的?
4。 五个元素为0就更没头绪了。
------
引用前面的帖子。
发信人: fengzhongdi (fzd), 信区: JobHunting
标 题: LinkedIn面试被老印郁闷到了.....
发信站: BBS 未名空间站 (Wed May 18 20:57:55 2011, 美东)
问了三个问题,第一个题目还算靠谱,就是在arraylist里面有乱序的数字,如何找出两个
数字使得和为0, O(n), 然后如何找出三个数字和为0, O(n^2), 四个数字和为0,这里我
卡了一下,在提示后给出了O(n^2)的解,然后如何找出五个数字和为0,我给出了O(n^3)的
解. | m***n 发帖数: 2154 | 2 2个的话,直接hashtable O(N),先排序,然后再left--> , <---right 操作O(N)+O(
NlgN)
3个的话,直接先排序NlgN, 然后求a+b=-c 对每一个元素做a+b=x操作 N^2
4个的话,也是排序,然后a+b+c=-d ,用前一步算法 N^3
.... | H***e 发帖数: 476 | 3 没看出来排序在这里有什么用
你已经有hashtable了,寻找一个元素已经是O(1)
【在 m***n 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 2个的话,直接hashtable O(N),先排序,然后再left--> , <---right 操作O(N)+O( : NlgN) : 3个的话,直接先排序NlgN, 然后求a+b=-c 对每一个元素做a+b=x操作 N^2 : 4个的话,也是排序,然后a+b+c=-d ,用前一步算法 N^3 : ....
| L***Q 发帖数: 508 | 4 一种延伸是不让你使用额外的storage,所以没法用hashtable。
三个数和为0,不用分正数负数,一个hashtable装全部数就行了。使用hashtable有一
个容易产生bug的地方:把一个数多次计算。比如-2 -1 4,不留神就会得到-2, -2,
4的组合。hashtable只告诉你某个数存在否,但没告诉你存在多少次。
不用hashtable的解法,sort然后头尾往中间扫描两端。最初是第一个array[0],然后
test array[1..n]中是否有2个数加起来等于-array[0]。接下来是array[1],test
array[2..n]中是否有2个数加起来等于-array[1]。时间复杂度仍然为O(N^2),空间复
杂度O(1)
【在 H***e 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 1。 一个array,找两个数字使得和为0,简单,只要用一个hashtable就可以了, 只需 : 要走一遍, O(n) time O(n) space : 2。 三个数字和为0, a+b+c = 0, 那么a+b+c = 0,那么 array当中必须有负数才行, : 把正数和负数分开,分别放到两个hashtable中: 正hashtable和负hashtable. : a+b+c = 0, 组合只有可能 ++- or --+, 所以对 每个正hashtable的元素a,看有没有 : 两元素加起来为'-a';对 每个负hashtable的元素b,看有没有两元素加起来为'-b',如 : 果有,则为解。 O(n^2) time, O(n) space : 3。 四个元素为0。这个是怎么有time O(n^2)的解的?space是多少的? : 4。 五个元素为0就更没头绪了。 : ------
| m***n 发帖数: 2154 | 5 对第一个没用,对后来的有用。
这个题目是两个元素和是n的简版。
a+b=0, 如果是sorted, 你左右操作指针,就可以找到那两个元素in O(n)
a+b+c=0,实际是要找a+b=-c, 针对每个元素, 用前面的办法操作就是n*o(n)
a+b+c+d =0 实际不就是a+b+c=-d, 同样用前一步的函数调用n回,用n*o(n^2)
应该这样可以吧。
【在 H***e 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 没看出来排序在这里有什么用 : 你已经有hashtable了,寻找一个元素已经是O(1)
| L***Q 发帖数: 508 | 6 原帖说4个数的算法是O(N^2)
【在 m***n 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 对第一个没用,对后来的有用。 : 这个题目是两个元素和是n的简版。 : a+b=0, 如果是sorted, 你左右操作指针,就可以找到那两个元素in O(n) : a+b+c=0,实际是要找a+b=-c, 针对每个元素, 用前面的办法操作就是n*o(n) : a+b+c+d =0 实际不就是a+b+c=-d, 同样用前一步的函数调用n回,用n*o(n^2) : 应该这样可以吧。
| m***n 发帖数: 2154 | 7 我能想到的办法还是先sort一下,
然后两个一组,一组从左,一组从右。
如果要为0, 必然左是负数, 右是正数。
一次只移动一个指针,相当一个左窗口,一个右窗口,滑动距离是1
【在 L***Q 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 原帖说4个数的算法是O(N^2)
| L***Q 发帖数: 508 | 8 如果一个数可以被计算多次,O(n^2)的算法还是可以的。计算每一对数的和,然后放入
hashtable。然后再对每一对数的和,在hashtable中查找是否有其负。时间复杂度O(n^
2),空间复杂度O(n^2)。
如果每个数只能算一次,那俺再想想
【在 L***Q 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 原帖说4个数的算法是O(N^2)
| m***n 发帖数: 2154 | 9 这应该符合O(n^2)的要求, n个数,对数只有n*(n-1)/2 对,扫描两次,应该可以的。
n^
【在 L***Q 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 如果一个数可以被计算多次,O(n^2)的算法还是可以的。计算每一对数的和,然后放入 : hashtable。然后再对每一对数的和,在hashtable中查找是否有其负。时间复杂度O(n^ : 2),空间复杂度O(n^2)。 : 如果每个数只能算一次,那俺再想想
| L***Q 发帖数: 508 | 10 这个有可能不对,例如-100 1 ... 99。一个答案是-100,1,2,97,但是右侧的两个数字
没在滑动距离为1 的窗口内
【在 m***n 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 我能想到的办法还是先sort一下, : 然后两个一组,一组从左,一组从右。 : 如果要为0, 必然左是负数, 右是正数。 : 一次只移动一个指针,相当一个左窗口,一个右窗口,滑动距离是1
| | | H***e 发帖数: 476 | 11 每个数肯定只能算一次
然后用hashtable找数,很可能找到自己
这个就是code不clean的地方
n^
【在 L***Q 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 如果一个数可以被计算多次,O(n^2)的算法还是可以的。计算每一对数的和,然后放入 : hashtable。然后再对每一对数的和,在hashtable中查找是否有其负。时间复杂度O(n^ : 2),空间复杂度O(n^2)。 : 如果每个数只能算一次,那俺再想想
| i**********e 发帖数: 1145 | 12 To find an answer where sum of four numbers equal to X, you can do it in O(n
^2) using some extra space. Basic idea is like what LeoZQ said, put all pair
sums in a hash table and search in the hash table. See below for a nice
idea:
http://stackoverflow.com/questions/3569504/find-four-elements-i
However, if you think carefully, if you wish to find all possible
quadruplets that sum to X, the worst case is O(n^3). This is because the
number of combinations grow in the order of O(n^3). (Credits to adjlist who figure this out.)
I have the problems two sum, 3sum, and 4sum here, and created test cases for
you to see if your program is correct. (you can submit Java or C++).
http://www.leetcode.com/onlinejudge | L***Q 发帖数: 508 | 13 大牛出现了,膜拜一下,保佑俺接下来interview人挡杀人佛挡杀佛
(n
pair
who figure this out.)
for
【在 i**********e 的大作中提到】![](/moin_static193/solenoid/img/up.png) : To find an answer where sum of four numbers equal to X, you can do it in O(n : ^2) using some extra space. Basic idea is like what LeoZQ said, put all pair : sums in a hash table and search in the hash table. See below for a nice : idea: : http://stackoverflow.com/questions/3569504/find-four-elements-i : However, if you think carefully, if you wish to find all possible : quadruplets that sum to X, the worst case is O(n^3). This is because the : number of combinations grow in the order of O(n^3). (Credits to adjlist who figure this out.) : I have the problems two sum, 3sum, and 4sum here, and created test cases for : you to see if your program is correct. (you can submit Java or C++).
| m***n 发帖数: 2154 | 14 这个会对啊, -100,1是在左窗口 , 2,97是右窗口。
如果左+右=0 ,就找到了。
否则 左+右>0, 右=右-1
否则 左=左+1
【在 L***Q 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 这个有可能不对,例如-100 1 ... 99。一个答案是-100,1,2,97,但是右侧的两个数字 : 没在滑动距离为1 的窗口内
| H***e 发帖数: 476 | 15
,
我把正数和负数分开,就是为了避免你说的bug
~~~~~~~~~~~
为什么这里不包括array[0] ?
【在 L***Q 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 一种延伸是不让你使用额外的storage,所以没法用hashtable。 : 三个数和为0,不用分正数负数,一个hashtable装全部数就行了。使用hashtable有一 : 个容易产生bug的地方:把一个数多次计算。比如-2 -1 4,不留神就会得到-2, -2, : 4的组合。hashtable只告诉你某个数存在否,但没告诉你存在多少次。 : 不用hashtable的解法,sort然后头尾往中间扫描两端。最初是第一个array[0],然后 : test array[1..n]中是否有2个数加起来等于-array[0]。接下来是array[1],test : array[2..n]中是否有2个数加起来等于-array[1]。时间复杂度仍然为O(N^2),空间复 : 杂度O(1)
| z****u 发帖数: 104 | 16 假设我们想找数列里有没有m个数的和为0
l = ceil(m / 2);
k = m - l;
首先,找到数列里每一个可能的l个数的组合,把他们的sum以及用到的数一起存到
hashtable,这个过程是O(n^l) time, O(n^l) space
重复以上过程,用k代替l,O(n^k) time, O(n^k) space
然后,遍历第一个hashtable,对里面的每一个元素
1, 查看第二个hashtable里有没有元素,它们的sum互为正负(O(1) time)
2, 如果有互为正负的数,看他们用到的数有没有重复(O(m))
对于给定的题目,m是常数,所以遍历部分的时间复杂度是O(n^l)
因为 l >= k,所以最终的时间复杂度是 O(n^l), l = ceil(m/2)
m = 2, O(n)
m = 3, O(n^2)
m = 4, O(n^2)
m = 5, O(n^3)
etc...
【在 H***e 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 1。 一个array,找两个数字使得和为0,简单,只要用一个hashtable就可以了, 只需 : 要走一遍, O(n) time O(n) space : 2。 三个数字和为0, a+b+c = 0, 那么a+b+c = 0,那么 array当中必须有负数才行, : 把正数和负数分开,分别放到两个hashtable中: 正hashtable和负hashtable. : a+b+c = 0, 组合只有可能 ++- or --+, 所以对 每个正hashtable的元素a,看有没有 : 两元素加起来为'-a';对 每个负hashtable的元素b,看有没有两元素加起来为'-b',如 : 果有,则为解。 O(n^2) time, O(n) space : 3。 四个元素为0。这个是怎么有time O(n^2)的解的?space是多少的? : 4。 五个元素为0就更没头绪了。 : ------
| L***Q 发帖数: 508 | 17 你的solution是看每个正数a,是否有2个负数之和等于这个-a;也看每个负数b,是否
有2个正数之和等于-b。
分开也会有bug的。比如-2 0 4。正数为4,然后在负数的hashtable里面查是否有2个负
数之和等于-4。那咋查hashtable才能避免把-2算2次呢?
一个办法:hashmap,保存数和它出现的次数。
【在 H***e 的大作中提到】![](/moin_static193/solenoid/img/up.png) : : , : 我把正数和负数分开,就是为了避免你说的bug : ~~~~~~~~~~~ : 为什么这里不包括array[0] ?
| m***n 发帖数: 2154 | 18 这个解法靠谱。。。
【在 z****u 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 假设我们想找数列里有没有m个数的和为0 : l = ceil(m / 2); : k = m - l; : 首先,找到数列里每一个可能的l个数的组合,把他们的sum以及用到的数一起存到 : hashtable,这个过程是O(n^l) time, O(n^l) space : 重复以上过程,用k代替l,O(n^k) time, O(n^k) space : 然后,遍历第一个hashtable,对里面的每一个元素 : 1, 查看第二个hashtable里有没有元素,它们的sum互为正负(O(1) time) : 2, 如果有互为正负的数,看他们用到的数有没有重复(O(m)) : 对于给定的题目,m是常数,所以遍历部分的时间复杂度是O(n^l)
| L***Q 发帖数: 508 | 19 Good idea
一个hashtable保存每两个数的和。另外要一个hashmap保存每个数在array里面出现的
次数。从hashtable里面找到2对之后,在hashmap里面check这4个数字出现的次数是否
valid。
【在 z****u 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 假设我们想找数列里有没有m个数的和为0 : l = ceil(m / 2); : k = m - l; : 首先,找到数列里每一个可能的l个数的组合,把他们的sum以及用到的数一起存到 : hashtable,这个过程是O(n^l) time, O(n^l) space : 重复以上过程,用k代替l,O(n^k) time, O(n^k) space : 然后,遍历第一个hashtable,对里面的每一个元素 : 1, 查看第二个hashtable里有没有元素,它们的sum互为正负(O(1) time) : 2, 如果有互为正负的数,看他们用到的数有没有重复(O(m)) : 对于给定的题目,m是常数,所以遍历部分的时间复杂度是O(n^l)
| H***e 发帖数: 476 | 20 “那咋查hashtable才能避免把-2算2次呢?”
这个就是那个two sum = 0问题啊
只走一次。
比如在放入元素之前,检查sum-itself在不在,之后再放itself进hashtable
【在 L***Q 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 你的solution是看每个正数a,是否有2个负数之和等于这个-a;也看每个负数b,是否 : 有2个正数之和等于-b。 : 分开也会有bug的。比如-2 0 4。正数为4,然后在负数的hashtable里面查是否有2个负 : 数之和等于-4。那咋查hashtable才能避免把-2算2次呢? : 一个办法:hashmap,保存数和它出现的次数。
| | | L***Q 发帖数: 508 | 21 俺还是没看出有什么区别。两个test case:
case 1: -2 -2 4 5
case 2: -2 4 5
分正负hashtable,两个test case你的hashtable放的东西一样
负hashtable只有-2,正hashtable有4和5
【在 H***e 的大作中提到】![](/moin_static193/solenoid/img/up.png) : “那咋查hashtable才能避免把-2算2次呢?” : 这个就是那个two sum = 0问题啊 : 只走一次。 : 比如在放入元素之前,检查sum-itself在不在,之后再放itself进hashtable
| H*****1 发帖数: 4815 | 22 为什么不是l = 2^ceil(log m)
then k = l/2
【在 z****u 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 假设我们想找数列里有没有m个数的和为0 : l = ceil(m / 2); : k = m - l; : 首先,找到数列里每一个可能的l个数的组合,把他们的sum以及用到的数一起存到 : hashtable,这个过程是O(n^l) time, O(n^l) space : 重复以上过程,用k代替l,O(n^k) time, O(n^k) space : 然后,遍历第一个hashtable,对里面的每一个元素 : 1, 查看第二个hashtable里有没有元素,它们的sum互为正负(O(1) time) : 2, 如果有互为正负的数,看他们用到的数有没有重复(O(m)) : 对于给定的题目,m是常数,所以遍历部分的时间复杂度是O(n^l)
| z****u 发帖数: 104 | 23 minimize max(l,k), subject to l + k = m; l belongs to N; k belongs to N
【在 H*****1 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 为什么不是l = 2^ceil(log m) : then k = l/2
| m***n 发帖数: 2154 | 24 public class CheckZeroSum {
public static void main(String args[]) {
int elem[]={-4,-3,-2,-1,2,3};
int elem2[] = {-5,-1,0,1,2,4,5};
checkZero(elem,4);
checkZero(elem2,2);
}
public static void checkZero(int[] elem, int n) {
//left, right
//left window size, right window size
int left = 0 ;
int right = elem.length-1;
int left_windowsize= n/2;
int right_windowsize= n-n/2;
while(left
int leftsum=0;
int rightsum=0;
for(int i=0;i
leftsum+=elem[left+i];
}
for(int j=0;j
rightsum+=elem[right-j];
}
if(leftsum+rightsum==0) {
for(int i=0;i
System.out.println(elem[left+i]+" ");
}
for(int j=0;j
System.out.println(elem[right-j]+" ");
}
left++;
right--;
}
else if(leftsum+rightsum>0) {
right--;
}
else
left++;
}
}
}
简单的实现, 至少对4和2都是对的 | m***n 发帖数: 2154 | |
|