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 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 用递归吧。 : 对每个数n,查是否存在 3 个数的和为(20-n) 等等。
|
b**y 发帖数: 805 | 6 展开讲讲?
【在 t********1 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 排列组合 算法
|
h**6 发帖数: 4160 | 7 先自加一次,变成n^2个数,然后判断新集合中有没有两个数的和等于指定数。
不过要把重复利用的加数去掉。 |
c******t 发帖数: 1500 | 8 此计甚妙!
【在 h**6 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 先自加一次,变成n^2个数,然后判断新集合中有没有两个数的和等于指定数。 : 不过要把重复利用的加数去掉。
|
s*****d 发帖数: 66 | 9 周郎此计妙哉! 不知孔明有何见解
【在 h**6 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 先自加一次,变成n^2个数,然后判断新集合中有没有两个数的和等于指定数。 : 不过要把重复利用的加数去掉。
|
A*********r 发帖数: 564 | 10 这道题可以算是careercup 中 19.11那道题的变体,原体是判断数组是否有两两之和等
于给定的数。
对于两两之和,先排序,然后用双指针,分别从头和尾开始扫描查看当前和,然后更新
指针位置。。
这道题也可以用类似的方法,分别外循环2个指针,内循环2个指针,分别查看当前的和
。算法复杂度应该是O(n^2), 不过好处是节省空间。。
【在 b**y 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 判断一个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 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 先自加一次,变成n^2个数,然后判断新集合中有没有两个数的和等于指定数。 : 不过要把重复利用的加数去掉。
|
p********7 发帖数: 549 | 12 应该用一个hashtable key是2个数的和,value是一个struct包括了这2个数的初始位置
,因为所有原始数据可能有重复,所以记录位置。
然后用hashtable查找的方法做,先查找 sum-key 是否存在,然后再插入。如果存在还
要获得这个key的以及sum-key的value 对比是否有重复。
【在 A*********r 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 这个关键是如何去掉重复利用的元素。。 : 如果新元素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 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 应该用一个hashtable key是2个数的和,value是一个struct包括了这2个数的初始位置 : ,因为所有原始数据可能有重复,所以记录位置。 : 然后用hashtable查找的方法做,先查找 sum-key 是否存在,然后再插入。如果存在还 : 要获得这个key的以及sum-key的value 对比是否有重复。
|
r***8 发帖数: 86 | 14 不错,这个题目如果改成,找到所有的组合,
又有什么办法,最快的全部找出呢?
【在 A*********r 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 这道题可以算是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 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 这个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 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 这个关键是如何去掉重复利用的元素。。 : 如果新元素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 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 不错,这个题目如果改成,找到所有的组合, : 又有什么办法,最快的全部找出呢?
|
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 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 看到所有这个字眼,我第一念头就会想到用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 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 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 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 这道题可以算是careercup 中 19.11那道题的变体,原体是判断数组是否有两两之和等 : 于给定的数。 : 对于两两之和,先排序,然后用双指针,分别从头和尾开始扫描查看当前和,然后更新 : 指针位置。。 : 这道题也可以用类似的方法,分别外循环2个指针,内循环2个指针,分别查看当前的和 : 。算法复杂度应该是O(n^2), 不过好处是节省空间。。
|
n******n 发帖数: 12088 | 21 not work.
【在 v***n 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 1 sort : 2 minimum 4 numbers added to see if it is possible to have a sum of 20 : 3 yada yada yada...
|