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 的大作中提到】
: 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 的大作中提到】
: 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 的大作中提到】
: 没看出来排序在这里有什么用
: 你已经有hashtable了，寻找一个元素已经是O(1)
| L***Q
发帖数: 508 | 6 原帖说4个数的算法是O(N^2)
【在 m***n 的大作中提到】
: 对第一个没用，对后来的有用。
: 这个题目是两个元素和是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 的大作中提到】
: 原帖说4个数的算法是O(N^2)
| L***Q
发帖数: 508 | 8 如果一个数可以被计算多次，O(n^2)的算法还是可以的。计算每一对数的和，然后放入
hashtable。然后再对每一对数的和，在hashtable中查找是否有其负。时间复杂度O(n^
2)，空间复杂度O(n^2)。
如果每个数只能算一次，那俺再想想
【在 L***Q 的大作中提到】
: 原帖说4个数的算法是O(N^2)
| m***n
发帖数: 2154 | 9 这应该符合O(n^2)的要求， n个数，对数只有n*(n-1)/2 对，扫描两次，应该可以的。
n^
【在 L***Q 的大作中提到】
: 如果一个数可以被计算多次，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 的大作中提到】
: 我能想到的办法还是先sort一下，
: 然后两个一组，一组从左，一组从右。
: 如果要为0， 必然左是负数， 右是正数。
: 一次只移动一个指针，相当一个左窗口，一个右窗口，滑动距离是1
| | | H***e
发帖数: 476 | 11 每个数肯定只能算一次
然后用hashtable找数，很可能找到自己
这个就是code不clean的地方
n^
【在 L***Q 的大作中提到】
: 如果一个数可以被计算多次，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 的大作中提到】
: 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 的大作中提到】
: 这个有可能不对，例如-100 1 ... 99。一个答案是-100,1,2,97，但是右侧的两个数字
: 没在滑动距离为1 的窗口内
| H***e
发帖数: 476 | 15
，
我把正数和负数分开，就是为了避免你说的bug
~~~~~~~~~~~
为什么这里不包括array[0] ?
【在 L***Q 的大作中提到】
: 一种延伸是不让你使用额外的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 的大作中提到】
: 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 的大作中提到】
:
: ，
: 我把正数和负数分开，就是为了避免你说的bug
: ~~~~~~~~~~~
: 为什么这里不包括array[0] ?
| m***n
发帖数: 2154 | 18 这个解法靠谱。。。
【在 z****u 的大作中提到】
: 假设我们想找数列里有没有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 的大作中提到】
: 假设我们想找数列里有没有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 的大作中提到】
: 你的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 的大作中提到】
: “那咋查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 的大作中提到】
: 假设我们想找数列里有没有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 的大作中提到】
: 为什么不是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 | |
|
