q******8
发帖数: 848 | 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.
有什么高效的解法吗？ | P*******U
发帖数: 203 | | l***i
发帖数: 1309 | 3 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). | u**r
发帖数: 663 | 4 n个数有n*(n-1)/2个2sum,把这些2sum记录在哈希表中,然后对每一个(target-2sum)值,
查哈希表看(target-2sum)是否在前面计算的2sum集合中,是的话就找到了要求的4sum.
时间空间复杂度都是O(n^2). | d********w
发帖数: 363 | 5 如果改成 a+b = c+d，也是同样的复杂度吧
值,
【在 u**r 的大作中提到】
: n个数有n*(n-1)/2个2sum,把这些2sum记录在哈希表中,然后对每一个(target-2sum)值,
: 查哈希表看(target-2sum)是否在前面计算的2sum集合中,是的话就找到了要求的4sum.
: 时间空间复杂度都是O(n^2).
| w***t
发帖数: 1474 | 6 万一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).
| r*****b
发帖数: 310 | 7 @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).
| r*****b
发帖数: 310 | 8 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; 这样是错的把
:
: 值,
| u**r
发帖数: 663 | 9 这个可以在找到匹配的时候附加判断吧。
哈希表里头可以记录每个2sum的元素index,找到匹配的时候判断以下index是否重复就
是了.
【在 w***t 的大作中提到】
: 万一2sum和target-2sum这两个sum包含同一个元素咋办。
: sum1 = a + b;
: sum2 = a + c;
: target = a + a + b + c; 这样是错的把
:
: 值,
| u**r
发帖数: 663 | 10 有重复的话可以在哈希表里头记录重复次数阿，比如你给的例子中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
:
: 值,
| | | i**********e
发帖数: 1145 | 11 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)) | m*****k
发帖数: 731 | 12 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)种不同的元素组合
| c********t
发帖数: 5706 | 13 真的吗？记得写过一个从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)种不同的元素组合
| c********t
发帖数: 5706 | 14 回顾了一下，那个只要求出一组解，这题是要所有解，不一样。
【在 c********t 的大作中提到】
: 真的吗？记得写过一个从N个数里找M个数，使和为<=S的最大值，复杂度为O(N*M*S).
: 求等于S应该一样吧。
:
: ,
| t****a
发帖数: 1212 | 15 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.
: 有什么高效的解法吗？
| c********t
发帖数: 5706 | 16 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
| c********t
发帖数: 5706 | 17 研究了一下你的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
:
: 值,
| q******8
发帖数: 848 | 18 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.
有什么高效的解法吗？ | P*******U
发帖数: 203 | 19 n^3的算法还是很好想的，更好的就要动动脑筋了 | l***i
发帖数: 1309 | 20 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). | | | u**r
发帖数: 663 | 21 n个数有n*(n-1)/2个2sum,把这些2sum记录在哈希表中,然后对每一个(target-2sum)值,
查哈希表看(target-2sum)是否在前面计算的2sum集合中,是的话就找到了要求的4sum.
时间空间复杂度都是O(n^2). | d********w
发帖数: 363 | 22 如果改成 a+b = c+d，也是同样的复杂度吧
值,
【在 u**r 的大作中提到】
: n个数有n*(n-1)/2个2sum,把这些2sum记录在哈希表中,然后对每一个(target-2sum)值,
: 查哈希表看(target-2sum)是否在前面计算的2sum集合中,是的话就找到了要求的4sum.
: 时间空间复杂度都是O(n^2).
| w***t
发帖数: 1474 | 23 万一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).
| r*****b
发帖数: 310 | 24 @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).
| r*****b
发帖数: 310 | 25 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; 这样是错的把
:
: 值,
| u**r
发帖数: 663 | 26 这个可以在找到匹配的时候附加判断吧。
哈希表里头可以记录每个2sum的元素index,找到匹配的时候判断以下index是否重复就
是了.
【在 w***t 的大作中提到】
: 万一2sum和target-2sum这两个sum包含同一个元素咋办。
: sum1 = a + b;
: sum2 = a + c;
: target = a + a + b + c; 这样是错的把
:
: 值,
| u**r
发帖数: 663 | 27 有重复的话可以在哈希表里头记录重复次数阿，比如你给的例子中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
:
: 值,
| i**********e
发帖数: 1145 | 28 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)) | m*****k
发帖数: 731 | 29 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)种不同的元素组合
| c********t
发帖数: 5706 | 30 真的吗？记得写过一个从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)种不同的元素组合
| | | c********t
发帖数: 5706 | 31 回顾了一下，那个只要求出一组解，这题是要所有解，不一样。
【在 c********t 的大作中提到】
: 真的吗？记得写过一个从N个数里找M个数，使和为<=S的最大值，复杂度为O(N*M*S).
: 求等于S应该一样吧。
:
: ,
| t****a
发帖数: 1212 | 32 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.
: 有什么高效的解法吗？
| c********t
发帖数: 5706 | 33 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
| c********t
发帖数: 5706 | 34 研究了一下你的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
:
: 值,
| p*****u
发帖数: 310 | 35 大家有什么结论？证明似乎是对的， worst case 是 o(n^3), 但是redcrab的解发也是
对的 worst case o(n^2lg(n)). | A****e
发帖数: 310 | 36 证明是对的.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)).
| p****e
发帖数: 3548 | 37 参考了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;
}
}; |
|
