b**y
发帖数: 805 | 1 判断一个set里是否有四个数的和等于一个target number.
eg. set {1,4,3,2,5,7,8,0,6} target number 20.
多谢 |
v***n
发帖数: 5085 | 2 1 sort
2 minimum 4 numbers added to see if it is possible to have a sum of 20
3 yada yada yada... |
M*m
发帖数: 141 | 3 用递归吧。
对每个数n，查是否存在 3 个数的和为(20-n) 等等。 |
t********1
发帖数: 3150 | |
b**y
发帖数: 805 | 5 递归最少的时间要用到O（n^3),那个interviewer问我能否再优化。。。
【在 M*m 的大作中提到】
: 用递归吧。
: 对每个数n，查是否存在 3 个数的和为(20-n) 等等。
|
b**y
发帖数: 805 | 6 展开讲讲？
【在 t********1 的大作中提到】
: 排列组合 算法
|
h**6
发帖数: 4160 | 7 先自加一次，变成n^2个数，然后判断新集合中有没有两个数的和等于指定数。
不过要把重复利用的加数去掉。 |
c******t
发帖数: 1500 | 8 此计甚妙！
【在 h**6 的大作中提到】
: 先自加一次，变成n^2个数，然后判断新集合中有没有两个数的和等于指定数。
: 不过要把重复利用的加数去掉。
|
s*****d
发帖数: 66 | 9 周郎此计妙哉！ 不知孔明有何见解
【在 h**6 的大作中提到】
: 先自加一次，变成n^2个数，然后判断新集合中有没有两个数的和等于指定数。
: 不过要把重复利用的加数去掉。
|
A*********r
发帖数: 564 | 10 这道题可以算是careercup 中 19.11那道题的变体，原体是判断数组是否有两两之和等
于给定的数。
对于两两之和，先排序，然后用双指针，分别从头和尾开始扫描查看当前和，然后更新
指针位置。。
这道题也可以用类似的方法，分别外循环2个指针，内循环2个指针，分别查看当前的和
。算法复杂度应该是O(n^2), 不过好处是节省空间。。
【在 b**y 的大作中提到】
: 判断一个set里是否有四个数的和等于一个target number.
: eg. set {1,4,3,2,5,7,8,0,6} target number 20.
: 多谢
|
|
|
A*********r
发帖数: 564 | 11 这个关键是如何去掉重复利用的元素。。
如果新元素B[k]=A[i]+A[j], k=(i+1)*N+j i
那么如果B[s]+B[t]为指定数的话，计算 s/N s%N, t/N,t%N 个不相等，估计就可以了
。。
这个算法复杂度也是O(N^2).
【在 h**6 的大作中提到】
: 先自加一次，变成n^2个数，然后判断新集合中有没有两个数的和等于指定数。
: 不过要把重复利用的加数去掉。
|
p********7
发帖数: 549 | 12 应该用一个hashtable key是2个数的和，value是一个struct包括了这2个数的初始位置
，因为所有原始数据可能有重复，所以记录位置。
然后用hashtable查找的方法做，先查找 sum-key 是否存在，然后再插入。如果存在还
要获得这个key的以及sum-key的value 对比是否有重复。
【在 A*********r 的大作中提到】
: 这个关键是如何去掉重复利用的元素。。
: 如果新元素B[k]=A[i]+A[j], k=(i+1)*N+j i: 那么如果B[s]+B[t]为指定数的话，计算 s/N s%N, t/N,t%N 个不相等，估计就可以了
: 。。
: 这个算法复杂度也是O(N^2).
|
A*********r
发帖数: 564 | 13 这个key 很有可能collision吧, 因为两两的和相等的数可能有很多啊。。
就是原始题型两两数之和也有这个问题，如果一个数重复多次的话，hashtable不是很
合适了，就要处理collision了。。
【在 p********7 的大作中提到】
: 应该用一个hashtable key是2个数的和，value是一个struct包括了这2个数的初始位置
: ，因为所有原始数据可能有重复，所以记录位置。
: 然后用hashtable查找的方法做，先查找 sum-key 是否存在，然后再插入。如果存在还
: 要获得这个key的以及sum-key的value 对比是否有重复。
|
r***8
发帖数: 86 | 14 不错，这个题目如果改成，找到所有的组合，
又有什么办法，最快的全部找出呢？
【在 A*********r 的大作中提到】
: 这道题可以算是careercup 中 19.11那道题的变体，原体是判断数组是否有两两之和等
: 于给定的数。
: 对于两两之和，先排序，然后用双指针，分别从头和尾开始扫描查看当前和，然后更新
: 指针位置。。
: 这道题也可以用类似的方法，分别外循环2个指针，内循环2个指针，分别查看当前的和
: 。算法复杂度应该是O(n^2), 不过好处是节省空间。。
|
p********7
发帖数: 549 | 15 有道理，但是可以处理下，比如key有重复加0.01，2个数加起来原来是12，下一次有12
就把他改为12.01存进去，查找的时候如果12存在，就再判断一次12.01是否存在，如果
存在就再加0.01
【在 A*********r 的大作中提到】
: 这个key 很有可能collision吧, 因为两两的和相等的数可能有很多啊。。
: 就是原始题型两两数之和也有这个问题，如果一个数重复多次的话，hashtable不是很
: 合适了，就要处理collision了。。
|
f****g
发帖数: 313 | 16 Hey AprilFlower, why we could guarantee no duplicated elements by computing
s/N s%N, t/N and t%N? thanks a lot!
【在 A*********r 的大作中提到】
: 这个关键是如何去掉重复利用的元素。。
: 如果新元素B[k]=A[i]+A[j], k=(i+1)*N+j i: 那么如果B[s]+B[t]为指定数的话，计算 s/N s%N, t/N,t%N 个不相等，估计就可以了
: 。。
: 这个算法复杂度也是O(N^2).
|
A*********r
发帖数: 564 | 17 看到所有这个字眼，我第一念头就会想到用DP, 呵呵，貌似是经典的subset sum
problem， 呵呵 NPC啊。。
【在 r***8 的大作中提到】
: 不错，这个题目如果改成，找到所有的组合，
: 又有什么办法，最快的全部找出呢？
|
r***8
发帖数: 86 | 18 没想到女孩玩算法也这样不得了啊
是啊，只能DP了，但针对此题，还是可以改进一下，找得快点
将这组数分成三组
第一组是大于 TARGET 一半并于小于等TARGET的数 我们定为A
第二组是大于TARGET 的四分之一，但小于一半 定为B
每三组是小于TARGET 四分之一 C
先对A数作一次LOOP DP，一个个试了，
只能从A取，B取一，C取两个
再对B一次LOOP DB，
B 取两个， C取两个
【在 A*********r 的大作中提到】
: 看到所有这个字眼，我第一念头就会想到用DP, 呵呵，貌似是经典的subset sum
: problem， 呵呵 NPC啊。。
|
A*********r
发帖数: 564 | 19 我的意思是新数组的index可以和原来组成这个数的两个index互相转换，这样的话就保
证了在新建立的数组中查找时，可以通过比较原来的坐标，来判断是否重复。。
比如原来数组 N=10， 那么两两相加组成的新数组有100个元素
新数组的 28号元素 就是原来数组的 2号 和 8号 元素而来
如果有另外一个21号元素与28号元素相加为target, 你可以断定原来数组2号元素被重
复利用了，所以不行。。同理81..89号元素也不行。。
不过回想这道题，如果需要sort新数组的话，估计这个方案就不行了，除非再建一个
hashtable。
computing
【在 f****g 的大作中提到】
: Hey AprilFlower, why we could guarantee no duplicated elements by computing
: s/N s%N, t/N and t%N? thanks a lot!
|
r**u
发帖数: 1567 | 20 我觉得你这算法的复杂度是O（n^3), inner loop是O(n)，因为那俩pointer只需
走过input array一次。但out loop需要O(n^2)吧。
paul那个解法也是O(n^3)吧。第一步算完俩俩之和(call it Sum array)有O(n^2)个元
素，每个元素最多重复n次，
那给定一个元素x in Sum array，如果有另一个元素y in Sum array，x+y = 要求的数
，x最多要比较n次。
【在 A*********r 的大作中提到】
: 这道题可以算是careercup 中 19.11那道题的变体，原体是判断数组是否有两两之和等
: 于给定的数。
: 对于两两之和，先排序，然后用双指针，分别从头和尾开始扫描查看当前和，然后更新
: 指针位置。。
: 这道题也可以用类似的方法，分别外循环2个指针，内循环2个指针，分别查看当前的和
: 。算法复杂度应该是O(n^2), 不过好处是节省空间。。
|
n******n
发帖数: 12088 | 21 not work.
【在 v***n 的大作中提到】
: 1 sort
: 2 minimum 4 numbers added to see if it is possible to have a sum of 20
: 3 yada yada yada...
|
