那种带棱的丝瓜是不是怕阳光? - 未名空间MITBBS历史存档

那种带棱的丝瓜是不是怕阳光?# gardening - 拈花惹草

q*82014-09-09 07:09

1 楼

Given an array S of n integers, are there elements a, b, c, and d in S such
that a + b + c + d = target? Find all unique quadruplets in the array which
gives the sum of target.
有什么高效的解法吗？

c*g2014-09-09 07:09

2 楼

想考虑买个好点的SUV开。但不确定买哪个？请给点建议:
A: BMW X5 2006 4.4
B: Range rover 2006
C: Benz M 2006
D: Highlander 2010
Range rover 是我的dream car。特别是坐在里面的view很高很爽。4万缺点听说车
子质量不太好。要经常的维修。
BMW X5 要3万左右，感觉性能比较稳定，质量比较好。
Benz M 和 New highlander 是备选项。
请给建议。
谢谢

p*e2014-09-09 07:09

3 楼

想自己装抽烟烟机，可是刚把橱柜打开，开始拆微波炉的时候就傻眼了。貌似前任房主
的抽油烟机也是排到外面的。可是排气管道在室内的接口是在橱柜偏右的地方，而微波
炉自己的排气口在中间，估计前任房主装的时候两个接不上，就想了个辙，找了个大小
刚合适的金属盒子，上面打个洞接到上面的出风口，下面再打个洞接到微波炉的出气口
；每次微波炉的油烟先进那个盒子，然后再通过管道排到外面去。为了密封好，上面是
先焊上然后贴胶布，所以很难拆，难道得买把焊枪先把这个金属盒子给割开？而且拆下
来以后不怎么好不好装range hood了，那个橱柜中间是一个大洞，而且排气管道口位置
靠右，怎么能把抽油烟机和管道接起来呢？买金属软管吗？
请各位指教，早点装好抽油烟机，我们全家老小也好早点搬家过去，开火做饭了。谢谢
谢谢
上面说得可能不清楚，上片片。

B*s2014-09-09 07:09

4 楼

大概五年前种了几棵,在阳光下的疯长叶和滕,开花后几天就蔫掉了.等到秋天凉时才接
了几个, 不过没有棱,表面是光滑的.夏天倒是有一棵藤钻到灌木底下, 接了好几个, 带
棱的.

P*U2014-09-09 07:09

5 楼

n^3的算法还是很好想的，更好的就要动动脑筋了

b*t2014-09-09 07:09

6 楼

highlander这个太监suv有啥好的？何况还不知道有没有自动加速问题
推荐你看看Tribeca，Murano，edge

p*e2014-09-09 07:09

7 楼

再来一张。

l*d2014-09-09 07:09

8 楼

我的棱角丝瓜也是八月份才开始结，圆丝瓜早就开始了。
棱角丝瓜太容易老，也太难削皮，以后再也不种了。
种了这么多丝瓜，还是圆胖丝瓜最好。

l*i2014-09-09 07:09

9 楼

Seems you can do O(n^2 log n)
For each pair of numbers, you can get a total of n^2 two-number sums.
Sort them cost O(n^2 log n)
Then you can use your target value T - each sum to get n^2 values sorted.
Then your job is to find whether there are two numbers that sum to any of
those n^2 values. This can be done by merge two sorted lists:
list1: a[i]+a[j] for each 1<=i,j<=n
list2: T-(a[i]+a[j]) for each 1<=i,j<=n
if list1 and list2 have a match, then a[i1]+a[j1] = T-(a[i2]+a[j2]) and that
is the same as a[i1]+a[j1]+a[i2]+a[j2]=T so i1,j1,i2,j2 are the four
numbers that sum up to T. Of course this might not be a solution because i1,
j1,i2,j2 might contain duplicates, but that is easy to detect and rule out.
Not sure if you can do O(n^2).

w*l2014-09-09 07:09

10 楼

珍惜生命，远离toyota

【在 c*********g 的大作中提到】

: 想考虑买个好点的SUV开。但不确定买哪个？请给点建议:
: A: BMW X5 2006 4.4
: B: Range rover 2006
: C: Benz M 2006
: D: Highlander 2010
: Range rover 是我的dream car。特别是坐在里面的view很高很爽。4万缺点听说车
: 子质量不太好。要经常的维修。
: BMW X5 要3万左右，感觉性能比较稳定，质量比较好。
: Benz M 和 New highlander 是备选项。
: 请给建议。

e*t2014-09-09 07:09

11 楼

用铁皮剪子就能剪开，不用焊枪。
http://www.amazon.com/Stanley-MaxSteel-14-562-8-Inch-Aviation/d

【在 p******e 的大作中提到】

: 想自己装抽烟烟机，可是刚把橱柜打开，开始拆微波炉的时候就傻眼了。貌似前任房主
: 的抽油烟机也是排到外面的。可是排气管道在室内的接口是在橱柜偏右的地方，而微波
: 炉自己的排气口在中间，估计前任房主装的时候两个接不上，就想了个辙，找了个大小
: 刚合适的金属盒子，上面打个洞接到上面的出风口，下面再打个洞接到微波炉的出气口
: ；每次微波炉的油烟先进那个盒子，然后再通过管道排到外面去。为了密封好，上面是
: 先焊上然后贴胶布，所以很难拆，难道得买把焊枪先把这个金属盒子给割开？而且拆下
: 来以后不怎么好不好装range hood了，那个橱柜中间是一个大洞，而且排气管道口位置
: 靠右，怎么能把抽油烟机和管道接起来呢？买金属软管吗？
: 请各位指教，早点装好抽油烟机，我们全家老小也好早点搬家过去，开火做饭了。谢谢
: 谢谢

u*r2014-09-09 07:09

12 楼

n个数有n*(n-1)/2个2sum,把这些2sum记录在哈希表中,然后对每一个(target-2sum)值,
查哈希表看(target-2sum)是否在前面计算的2sum集合中,是的话就找到了要求的4sum.
时间空间复杂度都是O(n^2).

a*u2014-09-09 07:09

13 楼

加点钱，买个2007 Escalade

【在 c*********g 的大作中提到】

: 想考虑买个好点的SUV开。但不确定买哪个？请给点建议:
: A: BMW X5 2006 4.4
: B: Range rover 2006
: C: Benz M 2006
: D: Highlander 2010
: Range rover 是我的dream car。特别是坐在里面的view很高很爽。4万缺点听说车
: 子质量不太好。要经常的维修。
: BMW X5 要3万左右，感觉性能比较稳定，质量比较好。
: Benz M 和 New highlander 是备选项。
: 请给建议。

e*t2014-09-09 07:09

14 楼

不过我建议你还是先把微波炉拿下来再说，不用掀动管道。说不定烟机也可以直接排到
盒子里，那就大省事了。

【在 p******e 的大作中提到】

: 想自己装抽烟烟机，可是刚把橱柜打开，开始拆微波炉的时候就傻眼了。貌似前任房主
: 的抽油烟机也是排到外面的。可是排气管道在室内的接口是在橱柜偏右的地方，而微波
: 炉自己的排气口在中间，估计前任房主装的时候两个接不上，就想了个辙，找了个大小
: 刚合适的金属盒子，上面打个洞接到上面的出风口，下面再打个洞接到微波炉的出气口
: ；每次微波炉的油烟先进那个盒子，然后再通过管道排到外面去。为了密封好，上面是
: 先焊上然后贴胶布，所以很难拆，难道得买把焊枪先把这个金属盒子给割开？而且拆下
: 来以后不怎么好不好装range hood了，那个橱柜中间是一个大洞，而且排气管道口位置
: 靠右，怎么能把抽油烟机和管道接起来呢？买金属软管吗？
: 请各位指教，早点装好抽油烟机，我们全家老小也好早点搬家过去，开火做饭了。谢谢
: 谢谢

d*w2014-09-09 07:09

15 楼

如果改成 a+b = c+d，也是同样的复杂度吧

值,

【在 u**r 的大作中提到】

: n个数有n*(n-1)/2个2sum,把这些2sum记录在哈希表中,然后对每一个(target-2sum)值,
: 查哈希表看(target-2sum)是否在前面计算的2sum集合中,是的话就找到了要求的4sum.
: 时间空间复杂度都是O(n^2).

F*t2014-09-09 07:09

16 楼

range rove再牛X,现在也是个咖喱车。就跟thinkpad一样，以前再怎么高档，现在也就
是大路货的形象。bmw和mb是豪华车，保养可能不省心。可能相对来说bmw x5稍微可靠
些。你也可以看看mdx嘛，还有infiniti的fx，也不错。至于highlander，这个只能算
中低档车。toyota的recall问题嘛，我觉得也不要太在意。哪个牌子的车没出过设计问
题？总的来说，toyota的质量还是最好的之一。

v*s2014-09-09 07:09

17 楼

装什么样的抽油烟机？中式的，需要把微波炉拿掉。微波炉的位置是油烟机的位置。你
需要软的弯管链接排气道。

【在 p******e 的大作中提到】

: 想自己装抽烟烟机，可是刚把橱柜打开，开始拆微波炉的时候就傻眼了。貌似前任房主
: 的抽油烟机也是排到外面的。可是排气管道在室内的接口是在橱柜偏右的地方，而微波
: 炉自己的排气口在中间，估计前任房主装的时候两个接不上，就想了个辙，找了个大小
: 刚合适的金属盒子，上面打个洞接到上面的出风口，下面再打个洞接到微波炉的出气口
: ；每次微波炉的油烟先进那个盒子，然后再通过管道排到外面去。为了密封好，上面是
: 先焊上然后贴胶布，所以很难拆，难道得买把焊枪先把这个金属盒子给割开？而且拆下
: 来以后不怎么好不好装range hood了，那个橱柜中间是一个大洞，而且排气管道口位置
: 靠右，怎么能把抽油烟机和管道接起来呢？买金属软管吗？
: 请各位指教，早点装好抽油烟机，我们全家老小也好早点搬家过去，开火做饭了。谢谢
: 谢谢

w*t2014-09-09 07:09

18 楼

万一2sum和target-2sum这两个sum包含同一个元素咋办。
sum1 = a + b;
sum2 = a + c;
target = a + a + b + c; 这样是错的把

值,

【在 u**r 的大作中提到】

: n个数有n*(n-1)/2个2sum,把这些2sum记录在哈希表中,然后对每一个(target-2sum)值,
: 查哈希表看(target-2sum)是否在前面计算的2sum集合中,是的话就找到了要求的4sum.
: 时间空间复杂度都是O(n^2).

d*s2014-09-09 07:09

19 楼

BMW X5 2006 4.4

h*82014-09-09 07:09

20 楼

把铁盒子拆了。
http://www.amazon.com/A048MX-Semi-Rigid-Flexible-Aluminum-clamp

【在 p******e 的大作中提到】

: 想自己装抽烟烟机，可是刚把橱柜打开，开始拆微波炉的时候就傻眼了。貌似前任房主
: 的抽油烟机也是排到外面的。可是排气管道在室内的接口是在橱柜偏右的地方，而微波
: 炉自己的排气口在中间，估计前任房主装的时候两个接不上，就想了个辙，找了个大小
: 刚合适的金属盒子，上面打个洞接到上面的出风口，下面再打个洞接到微波炉的出气口
: ；每次微波炉的油烟先进那个盒子，然后再通过管道排到外面去。为了密封好，上面是
: 先焊上然后贴胶布，所以很难拆，难道得买把焊枪先把这个金属盒子给割开？而且拆下
: 来以后不怎么好不好装range hood了，那个橱柜中间是一个大洞，而且排气管道口位置
: 靠右，怎么能把抽油烟机和管道接起来呢？买金属软管吗？
: 请各位指教，早点装好抽油烟机，我们全家老小也好早点搬家过去，开火做饭了。谢谢
: 谢谢

r*b2014-09-09 07:09

21 楼

@utar: this approach may not work, as we may find duplicates in the 2sums.
For instance, give an array [3, 6, 2, 7, 4, 5], and the target 18, we may
find there are three entries whose value is 9. If we include the time
complexity for resolving the conflicts, the time complexity is not O(n^2).
Here is my post with an implementation with O(N^2 * LogN) complexity.
http://basicalgos.blogspot.com/2012/03/12-4sum_11.html

值,

【在 u**r 的大作中提到】

: n个数有n*(n-1)/2个2sum,把这些2sum记录在哈希表中,然后对每一个(target-2sum)值,
: 查哈希表看(target-2sum)是否在前面计算的2sum集合中,是的话就找到了要求的4sum.
: 时间空间复杂度都是O(n^2).

c*g2014-09-09 07:09

22 楼

现在其实就是在选择 BMW X5, RANGE ROVER and Benz M 上面挣扎。
其实，很想买 RANGE ROVER, 但是用户评价多数都是这个车天天到dealer那里维修。
just a lemon.
BMW X5 第二选择。 OFF Road 能力比 range rover 差很多。
那么， BMW X5 3.0 VS 4.4 ?? 有什么建议没有，除了油耗。
4.4 真的会比3.0 爽很多吗？

p*e2014-09-09 07:09

23 楼

铁盒子不拿下来，微波炉好像没有办法拿下来，因为固定的螺丝是在铁盒子下面，铁盒
子又不能活动；抽油烟机也没有办法装上去。

【在 e********t 的大作中提到】

: 不过我建议你还是先把微波炉拿下来再说，不用掀动管道。说不定烟机也可以直接排到
: 盒子里，那就大省事了。

r*b2014-09-09 07:09

24 楼

Here is my implementation with O(N^2 logN) complexity. Comments are
welcome.
http://basicalgos.blogspot.com/2012/03/12-4sum_11.html

【在 w***t 的大作中提到】

: 万一2sum和target-2sum这两个sum包含同一个元素咋办。
: sum1 = a + b;
: sum2 = a + c;
: target = a + a + b + c; 这样是错的把
:
: 值,

s*i2014-09-09 07:09

25 楼

higherlander for sure，不是说它好，而是它最实用

【在 c*********g 的大作中提到】

: 现在其实就是在选择 BMW X5, RANGE ROVER and Benz M 上面挣扎。
: 其实，很想买 RANGE ROVER, 但是用户评价多数都是这个车天天到dealer那里维修。
: just a lemon.
: BMW X5 第二选择。 OFF Road 能力比 range rover 差很多。
: 那么， BMW X5 3.0 VS 4.4 ?? 有什么建议没有，除了油耗。
: 4.4 真的会比3.0 爽很多吗？

p*e2014-09-09 07:09

26 楼

中式的，或者神器，或者这一款：
http://www.ventingdirect.com/cavaliere-euro-ap238-ps13-30-30-st

【在 v***s 的大作中提到】

: 装什么样的抽油烟机？中式的，需要把微波炉拿掉。微波炉的位置是油烟机的位置。你
: 需要软的弯管链接排气道。

u*r2014-09-09 07:09

27 楼

这个可以在找到匹配的时候附加判断吧。
哈希表里头可以记录每个2sum的元素index,找到匹配的时候判断以下index是否重复就
是了.

【在 w***t 的大作中提到】

: 万一2sum和target-2sum这两个sum包含同一个元素咋办。
: sum1 = a + b;
: sum2 = a + c;
: target = a + a + b + c; 这样是错的把
:
: 值,

a*u2014-09-09 07:09

28 楼

我觉得BMW X5不错

【在 c*********g 的大作中提到】

: 现在其实就是在选择 BMW X5, RANGE ROVER and Benz M 上面挣扎。
: 其实，很想买 RANGE ROVER, 但是用户评价多数都是这个车天天到dealer那里维修。
: just a lemon.
: BMW X5 第二选择。 OFF Road 能力比 range rover 差很多。
: 那么， BMW X5 3.0 VS 4.4 ?? 有什么建议没有，除了油耗。
: 4.4 真的会比3.0 爽很多吗？

u*r2014-09-09 07:09

29 楼

有重复的话可以在哈希表里头记录重复次数阿，比如你给的例子中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]++;

【在 r*****b 的大作中提到】

: @utar: this approach may not work, as we may find duplicates in the 2sums.
: For instance, give an array [3, 6, 2, 7, 4, 5], and the target 18, we may
: find there are three entries whose value is 9. If we include the time
: complexity for resolving the conflicts, the time complexity is not O(n^2).
: Here is my post with an implementation with O(N^2 * LogN) complexity.
: http://basicalgos.blogspot.com/2012/03/12-4sum_11.html
:
: 值,

s*i2014-09-09 07:09

30 楼

有多少钱办多少事，我还想搞个法拉利开开呢，贷款30年月付也就几百块

【在 c*********g 的大作中提到】

: 现在其实就是在选择 BMW X5, RANGE ROVER and Benz M 上面挣扎。
: 其实，很想买 RANGE ROVER, 但是用户评价多数都是这个车天天到dealer那里维修。
: just a lemon.
: BMW X5 第二选择。 OFF Road 能力比 range rover 差很多。
: 那么， BMW X5 3.0 VS 4.4 ?? 有什么建议没有，除了油耗。
: 4.4 真的会比3.0 爽很多吗？

i*e2014-09-09 07:09

31 楼

Credits to adjlist for the following proof. This is a proof that printing
all possible combinations has the worst case complexity of O(N^3). However,
for printing any one of the combination, O(N^2) is possible by using extra
space (hash all possible pair-sums to a table).
这是详细证明--4sum(找全所有可能解)最坏情况下算法复杂度至少是O(N^3)　---
考虑下面的测试用例：
[1，2，3，4，5，...,n,
-1,-2,-3,...,-n-(n-1)-(n-2) ],target=0
从1,2,3,..,n里任意取三数，和都小于或等于n+(n-1)+(n-2). 也就是说这里面任意三
个正数都能匹配一个负数，使得和为0。i.e.这儿至少有n(n-1)(n-2)种不同的元素组合
其和为target.
结论：对于一个给定的n，我们至少可以构造一个含有O(n)元素的序列,其解的个数>O(
n^3).所以4sum问题的最坏算法复杂度至少是O(n^3).
另外，我们很容易就能找到O(n^3)的算法来解决这个4sum问题.从算法角度来讲，几乎
不可能找到比O(n^3)时间复杂度更优的解法了。
推广一下， K-sum问题的最坏算法复杂度应该就是O(n^(K-1))

b*t2014-09-09 07:09

32 楼

最实用？
这么个太监车，真不知道实用在哪儿
为啥x5就不实用？
疯田贩子想要推荐疯田总能找到理由

【在 s*i 的大作中提到】

: higherlander for sure，不是说它好，而是它最实用

m*k2014-09-09 07:09

33 楼

here in your case, the n is the largest abs(S[i]),
while the N in the question is the S.length

,

【在 i**********e 的大作中提到】

: Credits to adjlist for the following proof. This is a proof that printing
: all possible combinations has the worst case complexity of O(N^3). However,
: for printing any one of the combination, O(N^2) is possible by using extra
: space (hash all possible pair-sums to a table).
: 这是详细证明--4sum(找全所有可能解)最坏情况下算法复杂度至少是O(N^3)　---
: 考虑下面的测试用例：
: [1，2，3，4，5，...,n,
: -1,-2,-3,...,-n-(n-1)-(n-2) ],target=0
: 从1,2,3,..,n里任意取三数，和都小于或等于n+(n-1)+(n-2). 也就是说这里面任意三
: 个正数都能匹配一个负数，使得和为0。i.e.这儿至少有n(n-1)(n-2)种不同的元素组合

l*i2014-09-09 07:09

34 楼

CX-9 不错

【在 c*********g 的大作中提到】

: 现在其实就是在选择 BMW X5, RANGE ROVER and Benz M 上面挣扎。
: 其实，很想买 RANGE ROVER, 但是用户评价多数都是这个车天天到dealer那里维修。
: just a lemon.
: BMW X5 第二选择。 OFF Road 能力比 range rover 差很多。
: 那么， BMW X5 3.0 VS 4.4 ?? 有什么建议没有，除了油耗。
: 4.4 真的会比3.0 爽很多吗？

c*t2014-09-09 07:09

35 楼

真的吗？记得写过一个从N个数里找M个数，使和为<=S的最大值，复杂度为O(N*M*S).
求等于S应该一样吧。

,

【在 i**********e 的大作中提到】

: Credits to adjlist for the following proof. This is a proof that printing
: all possible combinations has the worst case complexity of O(N^3). However,
: for printing any one of the combination, O(N^2) is possible by using extra
: space (hash all possible pair-sums to a table).
: 这是详细证明--4sum(找全所有可能解)最坏情况下算法复杂度至少是O(N^3)　---
: 考虑下面的测试用例：
: [1，2，3，4，5，...,n,
: -1,-2,-3,...,-n-(n-1)-(n-2) ],target=0
: 从1,2,3,..,n里任意取三数，和都小于或等于n+(n-1)+(n-2). 也就是说这里面任意三
: 个正数都能匹配一个负数，使得和为0。i.e.这儿至少有n(n-1)(n-2)种不同的元素组合

l*i2014-09-09 07:09

36 楼

说说为什么是太监车

【在 b*****t 的大作中提到】

: 最实用？
: 这么个太监车，真不知道实用在哪儿
: 为啥x5就不实用？
: 疯田贩子想要推荐疯田总能找到理由

c*t2014-09-09 07:09

37 楼

回顾了一下，那个只要求出一组解，这题是要所有解，不一样。

【在 c********t 的大作中提到】

: 真的吗？记得写过一个从N个数里找M个数，使和为<=S的最大值，复杂度为O(N*M*S).
: 求等于S应该一样吧。
:
: ,

a*r2014-09-09 07:09

38 楼

4runner, 新款外形很阳刚

t*a2014-09-09 07:09

39 楼

DP solution, 复杂度为 4 * n * target * ?，其中? < 解的个数。如果高手有时间，
请帮我弄清楚复杂度是多少，先谢谢了。
DP formula
- f(i, j, target) = union([f(i-1, j-1, target-s_i), s_i], f(i-1, j, target))
- if i < j return []
- if target < 0 return []
- if j = 0 and target > 0 return []
- if j = 0 and target = 0 success
代码只有10行，详细参见
http://kangtu.me/~kangtu/study/interview.html#sec-13
程序中假定S为0..99，例子结果如下
(sumx 2 5) ; ((5 0) (4 1) (3 2))
(sumx 3 10) ; ((9 1 0) (8 2 0) (7 3 0) (7 2 1) (6 4 0) (6 3 1) (5 4 1) (5
3 2))
(sumx 4 10) ; ((7 2 1 0) (6 3 1 0) (5 4 1 0) (5 3 2 0) (4 3 2 1))
(sumx 5 30) ; ((24 3 2 1 0) (23 4 2 1 0) (22 5 2 1 0) (22 4 3 1 0) (21 6 2
1 0) (21 5 3 1 0) (21 4 3 2 0) (20 7 2 1 0) (20 6 3 1 0) (20 5 4 1 0) (20 5
3 2 0) (20 4 3 2 1) (19 8 2 1 0) (19 7 3 1 0) (19 6 4 1 0) (19 6 3 2 0) (19
5 4 2 0) (19 5 3 2 1) (18 9 2 1 0) (18 8 3 1 0) (18 7 4 1 0) (18 7 3 2 0) (
18 6 5 1 0) (18 6 4 2 0) (18 6 3 2 1) (18 5 4 3 0) (18 5 4 2 1) (17 10 2 1 0
) (17 9 3 1 0) (17 8 4 1 0) (17 8 3 2 0) (17 7 5 1 0) (17 7 4 2 0) (17 7 3 2
1) (17 6 5 2 0) (17 6 4 3 0) (17 6 4 2 1) (17 5 4 3 1) (16 11 2 1 0) (16 10
3 1 0) (16 9 4 1 0) (16 9 3 2 0) (16 8 5 1 0) (16 8 4 2 0) (16 8 3 2 1) (16
7 6 1 0) (16 7 5 2 0) (16 7 4 3 0) (16 7 4 2 1) (16 6 5 3 0) (16 6 5 2 1) (
16 6 4 3 1) (16 5 4 3 2) (15 12 2 1 0) (15 11 3 1 0) (15 10 4 1 0) (15 10 3
2 0) (15 9 5 1 0) (15 9 4 2 0) (15 9 3 2 1) (15 8 6 1 0) (15 8 5 2 0) (15 8
4 3 0) (15 8 4 2 1) (15 7 6 2 0) (15 7 5 3 0) (15 7 5 2 1) (15 7 4 3 1) (15
6 5 4 0) (15 6 5 3 1) (15 6 4 3 2) (14 13 2 1 0) (14 12 3 1 0) (14 11 4 1 0)
(14 11 3 2 0) (14 10 5 1 0) (14 10 4 2 0) (14 10 3 2 1) (14 9 6 1 0) (14 9
5 2 0) (14 9 4 3 0) (14 9 4 2 1) (14 8 7 1 0) (14 8 6 2 0) (14 8 5 3 0) (14
8 5 2 1) (14 8 4 3 1) (14 7 6 3 0) (14 7 6 2 1) (14 7 5 4 0) (14 7 5 3 1) (
14 7 4 3 2) (14 6 5 4 1) (14 6 5 3 2) (13 12 4 1 0) (13 12 3 2 0) (13 11 5 1
0) (13 11 4 2 0) (13 11 3 2 1) (13 10 6 1 0) (13 10 5 2 0) (13 10 4 3 0) (
13 10 4 2 1) (13 9 7 1 0) (13 9 6 2 0) (13 9 5 3 0) (13 9 5 2 1) (13 9 4 3 1
) (13 8 7 2 0) (13 8 6 3 0) (13 8 6 2 1) (13 8 5 4 0) (13 8 5 3 1) (13 8 4 3
2) (13 7 6 4 0) (13 7 6 3 1) (13 7 5 4 1) (13 7 5 3 2) (13 6 5 4 2) (12 11
6 1 0) (12 11 5 2 0) (12 11 4 3 0) (12 11 4 2 1) (12 10 7 1 0) (12 10 6 2 0)
(12 10 5 3 0) (12 10 5 2 1) (12 10 4 3 1) (12 9 8 1 0) (12 9 7 2 0) (12 9 6
3 0) (12 9 6 2 1) (12 9 5 4 0) (12 9 5 3 1) (12 9 4 3 2) (12 8 7 3 0) (12 8
7 2 1) (12 8 6 4 0) (12 8 6 3 1) (12 8 5 4 1) (12 8 5 3 2) (12 7 6 5 0) (12
7 6 4 1) (12 7 6 3 2) (12 7 5 4 2) (12 6 5 4 3) (11 10 8 1 0) (11 10 7 2 0)
(11 10 6 3 0) (11 10 6 2 1) (11 10 5 4 0) (11 10 5 3 1) (11 10 4 3 2) (11 9
8 2 0) (11 9 7 3 0) (11 9 7 2 1) (11 9 6 4 0) (11 9 6 3 1) (11 9 5 4 1) (11
9 5 3 2) (11 8 7 4 0) (11 8 7 3 1) (11 8 6 5 0) (11 8 6 4 1) (11 8 6 3 2) (
11 8 5 4 2) (11 7 6 5 1) (11 7 6 4 2) (11 7 5 4 3) (10 9 8 3 0) (10 9 8 2 1)
(10 9 7 4 0) (10 9 7 3 1) (10 9 6 5 0) (10 9 6 4 1) (10 9 6 3 2) (10 9 5 4
2) (10 8 7 5 0) (10 8 7 4 1) (10 8 7 3 2) (10 8 6 5 1) (10 8 6 4 2) (10 8 5
4 3) (10 7 6 5 2) (10 7 6 4 3) (9 8 7 6 0) (9 8 7 5 1) (9 8 7 4 2) (9 8 6 5
2) (9 8 6 4 3) (9 7 6 5 3) (8 7 6 5 4))

such
which

【在 q******8 的大作中提到】

: Given an array S of n integers, are there elements a, b, c, and d in S such
: that a + b + c + d = target? Find all unique quadruplets in the array which
: gives the sum of target.
: 有什么高效的解法吗？

b*t2014-09-09 07:09

40 楼

只能在公路上跑的suv
就算不叫太监车也差不多了
它那个awd和rav4是差不多的
比crv好不了多少
而且前后轮配重比也不合理
所以导致国内去除了awd的fwd车子小坡都上不去

【在 l*i 的大作中提到】

: 说说为什么是太监车

c*t2014-09-09 07:09

41 楼

10行太牛了，可惜读不懂pyton，能处理有重复的数情况吗？
比如 1,1,2，3,4 sum = 10.

))

【在 t****a 的大作中提到】

: DP solution, 复杂度为 4 * n * target * ?，其中? < 解的个数。如果高手有时间，
: 请帮我弄清楚复杂度是多少，先谢谢了。
: DP formula
: - f(i, j, target) = union([f(i-1, j-1, target-s_i), s_i], f(i-1, j, target))
: - if i < j return []
: - if target < 0 return []
: - if j = 0 and target > 0 return []
: - if j = 0 and target = 0 success
: 代码只有10行，详细参见
: http://kangtu.me/~kangtu/study/interview.html#sec-13

s*i2014-09-09 07:09

42 楼

呵呵，X5小，贵，维护费用高，这些都是它不实用的理由啊

【在 b*****t 的大作中提到】

: 最实用？
: 这么个太监车，真不知道实用在哪儿
: 为啥x5就不实用？
: 疯田贩子想要推荐疯田总能找到理由

c*t2014-09-09 07:09

43 楼

研究了一下你的codes, 很不错。不过最后的时候这句
find(result.begin(), result.end(), tmp)
又给复杂度*一个result.size(), 比如你给的例子[3, 6,2, 7, 4, 5]。result就是n^2
级的排列组合。
仔细又想了想,你试试把最后改成下面的，看行不行
for (j = begin; j <=end; j++){
if (twoSum[j].index1<=twoSum[i].index2) continue;
vector tmp;
tmp.push_back( num[ twoSum[i].index1] );
tmp.push_back( num[ twoSum[i].index2] );
tmp.push_back( num[ twoSum[j].index1] );
tmp.push_back( num[ twoSum[j].index2] );

result.push_back( tmp );
}

【在 r*****b 的大作中提到】

: @utar: this approach may not work, as we may find duplicates in the 2sums.
: For instance, give an array [3, 6, 2, 7, 4, 5], and the target 18, we may
: find there are three entries whose value is 9. If we include the time
: complexity for resolving the conflicts, the time complexity is not O(n^2).
: Here is my post with an implementation with O(N^2 * LogN) complexity.
: http://basicalgos.blogspot.com/2012/03/12-4sum_11.html
:
: 值,

s*i2014-09-09 07:09

44 楼

X5难道越野能力很强？

【在 b*****t 的大作中提到】

: 只能在公路上跑的suv
: 就算不叫太监车也差不多了
: 它那个awd和rav4是差不多的
: 比crv好不了多少
: 而且前后轮配重比也不合理
: 所以导致国内去除了awd的fwd车子小坡都上不去

q*82014-09-09 07:09

45 楼

Given an array S of n integers, are there elements a, b, c, and d in S such
that a + b + c + d = target? Find all unique quadruplets in the array which
gives the sum of target.
有什么高效的解法吗？

b*t2014-09-09 07:09

46 楼

x5虽然比那些常规越野车差不少，不过肯定比太监车要强的
还真有不少闲着没事的有钱人拿x5玩越野的，youtube上还有不少视频

【在 s*i 的大作中提到】

: X5难道越野能力很强？

P*U2014-09-09 07:09

47 楼

n^3的算法还是很好想的，更好的就要动动脑筋了

b*t2014-09-09 07:09

48 楼

想当然了不是
自己去查查highlander和x5哪个更大

【在 s*i 的大作中提到】

: 呵呵，X5小，贵，维护费用高，这些都是它不实用的理由啊

l*i2014-09-09 07:09

49 楼

Seems you can do O(n^2 log n)
For each pair of numbers, you can get a total of n^2 two-number sums.
Sort them cost O(n^2 log n)
Then you can use your target value T - each sum to get n^2 values sorted.
Then your job is to find whether there are two numbers that sum to any of
those n^2 values. This can be done by merge two sorted lists:
list1: a[i]+a[j] for each 1<=i,j<=n
list2: T-(a[i]+a[j]) for each 1<=i,j<=n
if list1 and list2 have a match, then a[i1]+a[j1] = T-(a[i2]+a[j2]) and that
is the same as a[i1]+a[j1]+a[i2]+a[j2]=T so i1,j1,i2,j2 are the four
numbers that sum up to T. Of course this might not be a solution because i1,
j1,i2,j2 might contain duplicates, but that is easy to detect and rule out.
Not sure if you can do O(n^2).

o*r2014-09-09 07:09

50 楼

新的X5好像没有旧款的好看。

【在 a**u 的大作中提到】

: 我觉得BMW X5不错

u*r2014-09-09 07:09

51 楼

n个数有n*(n-1)/2个2sum,把这些2sum记录在哈希表中,然后对每一个(target-2sum)值,
查哈希表看(target-2sum)是否在前面计算的2sum集合中,是的话就找到了要求的4sum.
时间空间复杂度都是O(n^2).

g*n2014-09-09 07:09

52 楼

2007 hummer h2，你列的只有range over能与之匹敌。
撞到h2，其余的都是玩具，特别是highlander这种不举的crossover

d*w2014-09-09 07:09

53 楼

如果改成 a+b = c+d，也是同样的复杂度吧

值,

【在 u**r 的大作中提到】

: n个数有n*(n-1)/2个2sum,把这些2sum记录在哈希表中,然后对每一个(target-2sum)值,
: 查哈希表看(target-2sum)是否在前面计算的2sum集合中,是的话就找到了要求的4sum.
: 时间空间复杂度都是O(n^2).

s*n2014-09-09 07:09

54 楼

X5 or Q7

【在 c*********g 的大作中提到】

: 现在其实就是在选择 BMW X5, RANGE ROVER and Benz M 上面挣扎。
: 其实，很想买 RANGE ROVER, 但是用户评价多数都是这个车天天到dealer那里维修。
: just a lemon.
: BMW X5 第二选择。 OFF Road 能力比 range rover 差很多。
: 那么， BMW X5 3.0 VS 4.4 ?? 有什么建议没有，除了油耗。
: 4.4 真的会比3.0 爽很多吗？

w*t2014-09-09 07:09

55 楼

万一2sum和target-2sum这两个sum包含同一个元素咋办。
sum1 = a + b;
sum2 = a + c;
target = a + a + b + c; 这样是错的把

值,

【在 u**r 的大作中提到】

: n个数有n*(n-1)/2个2sum,把这些2sum记录在哈希表中,然后对每一个(target-2sum)值,
: 查哈希表看(target-2sum)是否在前面计算的2sum集合中,是的话就找到了要求的4sum.
: 时间空间复杂度都是O(n^2).

o*e2014-09-09 07:09

56 楼

我刚上了2005 lexus gx470

r*b2014-09-09 07:09

57 楼

@utar: this approach may not work, as we may find duplicates in the 2sums.
For instance, give an array [3, 6, 2, 7, 4, 5], and the target 18, we may
find there are three entries whose value is 9. If we include the time
complexity for resolving the conflicts, the time complexity is not O(n^2).
Here is my post with an implementation with O(N^2 * LogN) complexity.
http://basicalgos.blogspot.com/2012/03/12-4sum_11.html

值,

【在 u**r 的大作中提到】

: n个数有n*(n-1)/2个2sum,把这些2sum记录在哈希表中,然后对每一个(target-2sum)值,
: 查哈希表看(target-2sum)是否在前面计算的2sum集合中,是的话就找到了要求的4sum.
: 时间空间复杂度都是O(n^2).

d*a2014-09-09 07:09

58 楼

Tahoe啊，SUV king

r*b2014-09-09 07:09

59 楼

Here is my implementation with O(N^2 logN) complexity. Comments are
welcome.
http://basicalgos.blogspot.com/2012/03/12-4sum_11.html

【在 w***t 的大作中提到】

: 万一2sum和target-2sum这两个sum包含同一个元素咋办。
: sum1 = a + b;
: sum2 = a + c;
: target = a + a + b + c; 这样是错的把
:
: 值,

a*u2014-09-09 07:09

60 楼

嘿嘿，估计版上没几个人开这车。

【在 d********a 的大作中提到】

: Tahoe啊，SUV king

u*r2014-09-09 07:09

61 楼

这个可以在找到匹配的时候附加判断吧。
哈希表里头可以记录每个2sum的元素index,找到匹配的时候判断以下index是否重复就
是了.

【在 w***t 的大作中提到】

: 万一2sum和target-2sum这两个sum包含同一个元素咋办。
: sum1 = a + b;
: sum2 = a + c;
: target = a + a + b + c; 这样是错的把
:
: 值,

i*r2014-09-09 07:09

62 楼

你这辈子真的会offroad哪怕一次么？

【在 c*********g 的大作中提到】

: 现在其实就是在选择 BMW X5, RANGE ROVER and Benz M 上面挣扎。
: 其实，很想买 RANGE ROVER, 但是用户评价多数都是这个车天天到dealer那里维修。
: just a lemon.
: BMW X5 第二选择。 OFF Road 能力比 range rover 差很多。
: 那么， BMW X5 3.0 VS 4.4 ?? 有什么建议没有，除了油耗。
: 4.4 真的会比3.0 爽很多吗？

u*r2014-09-09 07:09

63 楼

有重复的话可以在哈希表里头记录重复次数阿，比如你给的例子中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]++;

【在 r*****b 的大作中提到】

: @utar: this approach may not work, as we may find duplicates in the 2sums.
: For instance, give an array [3, 6, 2, 7, 4, 5], and the target 18, we may
: find there are three entries whose value is 9. If we include the time
: complexity for resolving the conflicts, the time complexity is not O(n^2).
: Here is my post with an implementation with O(N^2 * LogN) complexity.
: http://basicalgos.blogspot.com/2012/03/12-4sum_11.html
:
: 值,

y*m2014-09-09 07:09

64 楼

Highlander's 4x4 is a fake one like CRV.

【在 c*********g 的大作中提到】

: 现在其实就是在选择 BMW X5, RANGE ROVER and Benz M 上面挣扎。
: 其实，很想买 RANGE ROVER, 但是用户评价多数都是这个车天天到dealer那里维修。
: just a lemon.
: BMW X5 第二选择。 OFF Road 能力比 range rover 差很多。
: 那么， BMW X5 3.0 VS 4.4 ?? 有什么建议没有，除了油耗。
: 4.4 真的会比3.0 爽很多吗？

i*e2014-09-09 07:09

65 楼

Credits to adjlist for the following proof. This is a proof that printing
all possible combinations has the worst case complexity of O(N^3). However,
for printing any one of the combination, O(N^2) is possible by using extra
space (hash all possible pair-sums to a table).
这是详细证明--4sum(找全所有可能解)最坏情况下算法复杂度至少是O(N^3)　---
考虑下面的测试用例：
[1，2，3，4，5，...,n,
-1,-2,-3,...,-n-(n-1)-(n-2) ],target=0
从1,2,3,..,n里任意取三数，和都小于或等于n+(n-1)+(n-2). 也就是说这里面任意三
个正数都能匹配一个负数，使得和为0。i.e.这儿至少有n(n-1)(n-2)种不同的元素组合
其和为target.
结论：对于一个给定的n，我们至少可以构造一个含有O(n)元素的序列,其解的个数>O(
n^3).所以4sum问题的最坏算法复杂度至少是O(n^3).
另外，我们很容易就能找到O(n^3)的算法来解决这个4sum问题.从算法角度来讲，几乎
不可能找到比O(n^3)时间复杂度更优的解法了。
推广一下， K-sum问题的最坏算法复杂度应该就是O(n^(K-1))

T*g2014-09-09 07:09

66 楼

2005/2006 Porsche Cayenne S

m*k2014-09-09 07:09

67 楼

here in your case, the n is the largest abs(S[i]),
while the N in the question is the S.length

,

【在 i**********e 的大作中提到】

: Credits to adjlist for the following proof. This is a proof that printing
: all possible combinations has the worst case complexity of O(N^3). However,
: for printing any one of the combination, O(N^2) is possible by using extra
: space (hash all possible pair-sums to a table).
: 这是详细证明--4sum(找全所有可能解)最坏情况下算法复杂度至少是O(N^3)　---
: 考虑下面的测试用例：
: [1，2，3，4，5，...,n,
: -1,-2,-3,...,-n-(n-1)-(n-2) ],target=0
: 从1,2,3,..,n里任意取三数，和都小于或等于n+(n-1)+(n-2). 也就是说这里面任意三
: 个正数都能匹配一个负数，使得和为0。i.e.这儿至少有n(n-1)(n-2)种不同的元素组合

b*r2014-09-09 07:09

68 楼

都有瑕疵，Ｐｏｒｃｈｅ　Ｃａｙｅｎｎｅ好一点

【在 c*********g 的大作中提到】

: 现在其实就是在选择 BMW X5, RANGE ROVER and Benz M 上面挣扎。
: 其实，很想买 RANGE ROVER, 但是用户评价多数都是这个车天天到dealer那里维修。
: just a lemon.
: BMW X5 第二选择。 OFF Road 能力比 range rover 差很多。
: 那么， BMW X5 3.0 VS 4.4 ?? 有什么建议没有，除了油耗。
: 4.4 真的会比3.0 爽很多吗？

c*t2014-09-09 07:09

69 楼

真的吗？记得写过一个从N个数里找M个数，使和为<=S的最大值，复杂度为O(N*M*S).
求等于S应该一样吧。

,

【在 i**********e 的大作中提到】

: Credits to adjlist for the following proof. This is a proof that printing
: all possible combinations has the worst case complexity of O(N^3). However,
: for printing any one of the combination, O(N^2) is possible by using extra
: space (hash all possible pair-sums to a table).
: 这是详细证明--4sum(找全所有可能解)最坏情况下算法复杂度至少是O(N^3)　---
: 考虑下面的测试用例：
: [1，2，3，4，5，...,n,
: -1,-2,-3,...,-n-(n-1)-(n-2) ],target=0
: 从1,2,3,..,n里任意取三数，和都小于或等于n+(n-1)+(n-2). 也就是说这里面任意三
: 个正数都能匹配一个负数，使得和为0。i.e.这儿至少有n(n-1)(n-2)种不同的元素组合

b*t2014-09-09 07:09

70 楼

只有疯田贩子的建议最值得看是吧？
黑你奶奶的大头鬼
你哪只眼睛看到我黑日车了？
我说的可都是事实
大都都是针对疯田贩子的

c*t2014-09-09 07:09

71 楼

回顾了一下，那个只要求出一组解，这题是要所有解，不一样。

【在 c********t 的大作中提到】

: 真的吗？记得写过一个从N个数里找M个数，使和为<=S的最大值，复杂度为O(N*M*S).
: 求等于S应该一样吧。
:
: ,

e*d2014-09-09 07:09

72 楼

it is very stupid to buy a car on a 30-year loan.

【在 s*i 的大作中提到】

: 有多少钱办多少事，我还想搞个法拉利开开呢，贷款30年月付也就几百块

t*a2014-09-09 07:09

73 楼

DP solution, 复杂度为 4 * n * target * ?，其中? < 解的个数。如果高手有时间，
请帮我弄清楚复杂度是多少，先谢谢了。
DP formula
- f(i, j, target) = union([f(i-1, j-1, target-s_i), s_i], f(i-1, j, target))
- if i < j return []
- if target < 0 return []
- if j = 0 and target > 0 return []
- if j = 0 and target = 0 success
代码只有10行，详细参见
http://kangtu.me/~kangtu/study/interview.html#sec-13
程序中假定S为0..99，例子结果如下
(sumx 2 5) ; ((5 0) (4 1) (3 2))
(sumx 3 10) ; ((9 1 0) (8 2 0) (7 3 0) (7 2 1) (6 4 0) (6 3 1) (5 4 1) (5
3 2))
(sumx 4 10) ; ((7 2 1 0) (6 3 1 0) (5 4 1 0) (5 3 2 0) (4 3 2 1))
(sumx 5 30) ; ((24 3 2 1 0) (23 4 2 1 0) (22 5 2 1 0) (22 4 3 1 0) (21 6 2
1 0) (21 5 3 1 0) (21 4 3 2 0) (20 7 2 1 0) (20 6 3 1 0) (20 5 4 1 0) (20 5
3 2 0) (20 4 3 2 1) (19 8 2 1 0) (19 7 3 1 0) (19 6 4 1 0) (19 6 3 2 0) (19
5 4 2 0) (19 5 3 2 1) (18 9 2 1 0) (18 8 3 1 0) (18 7 4 1 0) (18 7 3 2 0) (
18 6 5 1 0) (18 6 4 2 0) (18 6 3 2 1) (18 5 4 3 0) (18 5 4 2 1) (17 10 2 1 0
) (17 9 3 1 0) (17 8 4 1 0) (17 8 3 2 0) (17 7 5 1 0) (17 7 4 2 0) (17 7 3 2
1) (17 6 5 2 0) (17 6 4 3 0) (17 6 4 2 1) (17 5 4 3 1) (16 11 2 1 0) (16 10
3 1 0) (16 9 4 1 0) (16 9 3 2 0) (16 8 5 1 0) (16 8 4 2 0) (16 8 3 2 1) (16
7 6 1 0) (16 7 5 2 0) (16 7 4 3 0) (16 7 4 2 1) (16 6 5 3 0) (16 6 5 2 1) (
16 6 4 3 1) (16 5 4 3 2) (15 12 2 1 0) (15 11 3 1 0) (15 10 4 1 0) (15 10 3
2 0) (15 9 5 1 0) (15 9 4 2 0) (15 9 3 2 1) (15 8 6 1 0) (15 8 5 2 0) (15 8
4 3 0) (15 8 4 2 1) (15 7 6 2 0) (15 7 5 3 0) (15 7 5 2 1) (15 7 4 3 1) (15
6 5 4 0) (15 6 5 3 1) (15 6 4 3 2) (14 13 2 1 0) (14 12 3 1 0) (14 11 4 1 0)
(14 11 3 2 0) (14 10 5 1 0) (14 10 4 2 0) (14 10 3 2 1) (14 9 6 1 0) (14 9
5 2 0) (14 9 4 3 0) (14 9 4 2 1) (14 8 7 1 0) (14 8 6 2 0) (14 8 5 3 0) (14
8 5 2 1) (14 8 4 3 1) (14 7 6 3 0) (14 7 6 2 1) (14 7 5 4 0) (14 7 5 3 1) (
14 7 4 3 2) (14 6 5 4 1) (14 6 5 3 2) (13 12 4 1 0) (13 12 3 2 0) (13 11 5 1
0) (13 11 4 2 0) (13 11 3 2 1) (13 10 6 1 0) (13 10 5 2 0) (13 10 4 3 0) (
13 10 4 2 1) (13 9 7 1 0) (13 9 6 2 0) (13 9 5 3 0) (13 9 5 2 1) (13 9 4 3 1
) (13 8 7 2 0) (13 8 6 3 0) (13 8 6 2 1) (13 8 5 4 0) (13 8 5 3 1) (13 8 4 3
2) (13 7 6 4 0) (13 7 6 3 1) (13 7 5 4 1) (13 7 5 3 2) (13 6 5 4 2) (12 11
6 1 0) (12 11 5 2 0) (12 11 4 3 0) (12 11 4 2 1) (12 10 7 1 0) (12 10 6 2 0)
(12 10 5 3 0) (12 10 5 2 1) (12 10 4 3 1) (12 9 8 1 0) (12 9 7 2 0) (12 9 6
3 0) (12 9 6 2 1) (12 9 5 4 0) (12 9 5 3 1) (12 9 4 3 2) (12 8 7 3 0) (12 8
7 2 1) (12 8 6 4 0) (12 8 6 3 1) (12 8 5 4 1) (12 8 5 3 2) (12 7 6 5 0) (12
7 6 4 1) (12 7 6 3 2) (12 7 5 4 2) (12 6 5 4 3) (11 10 8 1 0) (11 10 7 2 0)
(11 10 6 3 0) (11 10 6 2 1) (11 10 5 4 0) (11 10 5 3 1) (11 10 4 3 2) (11 9
8 2 0) (11 9 7 3 0) (11 9 7 2 1) (11 9 6 4 0) (11 9 6 3 1) (11 9 5 4 1) (11
9 5 3 2) (11 8 7 4 0) (11 8 7 3 1) (11 8 6 5 0) (11 8 6 4 1) (11 8 6 3 2) (
11 8 5 4 2) (11 7 6 5 1) (11 7 6 4 2) (11 7 5 4 3) (10 9 8 3 0) (10 9 8 2 1)
(10 9 7 4 0) (10 9 7 3 1) (10 9 6 5 0) (10 9 6 4 1) (10 9 6 3 2) (10 9 5 4
2) (10 8 7 5 0) (10 8 7 4 1) (10 8 7 3 2) (10 8 6 5 1) (10 8 6 4 2) (10 8 5
4 3) (10 7 6 5 2) (10 7 6 4 3) (9 8 7 6 0) (9 8 7 5 1) (9 8 7 4 2) (9 8 6 5
2) (9 8 6 4 3) (9 7 6 5 3) (8 7 6 5 4))

such
which

【在 q******8 的大作中提到】

: Given an array S of n integers, are there elements a, b, c, and d in S such
: that a + b + c + d = target? Find all unique quadruplets in the array which
: gives the sum of target.
: 有什么高效的解法吗？

d*u2014-09-09 07:09

74 楼

为啥不上2011 jeep grand chrokee啊？既能越野，又实用。

c*t2014-09-09 07:09

75 楼

10行太牛了，可惜读不懂pyton，能处理有重复的数情况吗？
比如 1,1,2，3,4 sum = 10.

))

【在 t****a 的大作中提到】

: DP solution, 复杂度为 4 * n * target * ?，其中? < 解的个数。如果高手有时间，
: 请帮我弄清楚复杂度是多少，先谢谢了。
: DP formula
: - f(i, j, target) = union([f(i-1, j-1, target-s_i), s_i], f(i-1, j, target))
: - if i < j return []
: - if target < 0 return []
: - if j = 0 and target > 0 return []
: - if j = 0 and target = 0 success
: 代码只有10行，详细参见
: http://kangtu.me/~kangtu/study/interview.html#sec-13

d*22014-09-09 07:09

76 楼

dream car: range rover.　然后回来报告说此车可靠性不好的都是谣言。

c*t2014-09-09 07:09

77 楼

研究了一下你的codes, 很不错。不过最后的时候这句
find(result.begin(), result.end(), tmp)
又给复杂度*一个result.size(), 比如你给的例子[3, 6,2, 7, 4, 5]。result就是n^2
级的排列组合。
仔细又想了想,你试试把最后改成下面的，看行不行
for (j = begin; j <=end; j++){
if (twoSum[j].index1<=twoSum[i].index2) continue;
vector tmp;
tmp.push_back( num[ twoSum[i].index1] );
tmp.push_back( num[ twoSum[i].index2] );
tmp.push_back( num[ twoSum[j].index1] );
tmp.push_back( num[ twoSum[j].index2] );

result.push_back( tmp );
}

【在 r*****b 的大作中提到】

: @utar: this approach may not work, as we may find duplicates in the 2sums.
: For instance, give an array [3, 6, 2, 7, 4, 5], and the target 18, we may
: find there are three entries whose value is 9. If we include the time
: complexity for resolving the conflicts, the time complexity is not O(n^2).
: Here is my post with an implementation with O(N^2 * LogN) complexity.
: http://basicalgos.blogspot.com/2012/03/12-4sum_11.html
:
: 值,

o*p2014-09-09 07:09

78 楼

BMW X5. 2006 MB M-class is too small. MB GL450 is good, though.

【在 c*********g 的大作中提到】

: 现在其实就是在选择 BMW X5, RANGE ROVER and Benz M 上面挣扎。
: 其实，很想买 RANGE ROVER, 但是用户评价多数都是这个车天天到dealer那里维修。
: just a lemon.
: BMW X5 第二选择。 OFF Road 能力比 range rover 差很多。
: 那么， BMW X5 3.0 VS 4.4 ?? 有什么建议没有，除了油耗。
: 4.4 真的会比3.0 爽很多吗？

p*u2014-09-09 07:09

79 楼

大家有什么结论？证明似乎是对的， worst case 是 o(n^3), 但是redcrab的解发也是
对的 worst case o(n^2lg(n)).

S*s2014-09-09 07:09

80 楼

强烈推荐maruno
太赞了

【在 c*********g 的大作中提到】

: 现在其实就是在选择 BMW X5, RANGE ROVER and Benz M 上面挣扎。
: 其实，很想买 RANGE ROVER, 但是用户评价多数都是这个车天天到dealer那里维修。
: just a lemon.
: BMW X5 第二选择。 OFF Road 能力比 range rover 差很多。
: 那么， BMW X5 3.0 VS 4.4 ?? 有什么建议没有，除了油耗。
: 4.4 真的会比3.0 爽很多吗？

A*e2014-09-09 07:09

81 楼

证明是对的.redcrab的程序我是这么理解的，里面有这么一段
// we need to find the range of the TowSums that have the same value.
所以如果把所有same value的这些都找出来，复杂度就变成了O(N)，而不是O(lgN^2)=O
(lgN).总的复杂度就变成了O(N^3).

【在 p*****u 的大作中提到】

: 大家有什么结论？证明似乎是对的， worst case 是 o(n^3), 但是redcrab的解发也是
: 对的 worst case o(n^2lg(n)).

o*n2014-09-09 07:09

82 楼

outback

p*e2014-09-09 07:09

83 楼

参考了redcrab的，改了一下，再发
class Solution {
public:

vector > fourSum(vector &num, int target) {
// Start typing your C/C++ solution below
// DO NOT write int main() function
int depth = 0;
int size = num.size();
sort(num.begin(), num.end());
vector > rlt;
for(int i = 0; i < size - 3; i++)
{
int itempsum = num[i];
if(itempsum > target/4.) break;
for(int j = i+1; j < size - 2; j++)
{
int jtempsum = itempsum + num[j];
if(jtempsum > target/2.) break;
for(int k = j + 1; k < size - 1; k++)
{
int ktempsum = jtempsum + num[k];
if(ktempsum > 3.*target/4.) break;
for(int l = k + 1; l < size; l++)
{
int ltempsum = ktempsum + num[l];
if(ltempsum > target) break;
if(ltempsum == target)
{
vector temprlt;
temprlt.push_back(num[i]);
temprlt.push_back(num[j]);
temprlt.push_back(num[k]);
temprlt.push_back(num[l]);
if (find(rlt.begin(), rlt.end(), temprlt) == rlt.end())
rlt.push_back(temprlt);
}
}
}
}
}
return rlt;
}
};

y*n2014-09-09 07:09

84 楼

这车贬值很快。
不保值

【在 S****s 的大作中提到】

: 强烈推荐maruno
: 太赞了

c*a2014-09-09 07:09

85 楼

可以考虑highlander。不要买4缸的，新款的太重了（比老款重了1000磅）。有雪的地
区4驱的比较好。这个时候好砍价，呵呵。
上个小坡还行，
http://www.youtube.com/watch?v=5qF4TNDjKC8

c*a2014-09-09 07:09

86 楼

co 赞，lol

【在 S****s 的大作中提到】

: 强烈推荐maruno
: 太赞了

r*n2014-09-09 07:09

87 楼

FX35 or FX45

p*o2014-09-09 07:09

88 楼

Escalade 强烈推荐

k*e2014-09-09 07:09

89 楼

大切

c*u2014-09-09 07:09

90 楼

advice based on person experience:
stay away from land rover. it will make you crazy if you are a fastidious
person.
try bmw or as someone said porche.