i**********e
发帖数: 1145 | 1 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.
结论： 对... 阅读全帖 |
|
i**********e
发帖数: 1145 | 2 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.
结论： 对... 阅读全帖 |
|
s*******m
发帖数: 228 | 3 2Sum, 3Sum, 4Sum
稍微有点变化的是, array中数字是0-10, target也是0-10的. 要求输出在数组中最先
遇到的
满足条件的
pair(2sum)
triplet(3sum)
4个数字组(4sum) |
|
u**r
发帖数: 663 | 4 n个数有n*(n-1)/2个2sum,把这些2sum记录在哈希表中,然后对每一个(target-2sum)值,
查哈希表看(target-2sum)是否在前面计算的2sum集合中,是的话就找到了要求的4sum.
时间空间复杂度都是O(n^2). |
|
u**r
发帖数: 663 | 5 n个数有n*(n-1)/2个2sum,把这些2sum记录在哈希表中,然后对每一个(target-2sum)值,
查哈希表看(target-2sum)是否在前面计算的2sum集合中,是的话就找到了要求的4sum.
时间空间复杂度都是O(n^2). |
|
r*****e
发帖数: 30 | 6 the lowerbound of 4sum runtime is O(n^3). |
|
r*****e
发帖数: 30 | 7 the lowerbound of 4sum runtime is O(n^3). |
|
c********p
发帖数: 1969 | 8 leetcode变聪明了吧？
我的4sum明明可以过大oj的，怎么现在过不了了？
谁有好点的版本？
我的版本是：
把两两的和，放到hashtable里，有重复数字，也重复一遍，hashtable里的值是int[2]
, 每个值表示index而不是值。key是sum。
两两的sum在int[] sum中再存一遍。然后sort。里边有重复的。
return的结果放到hashset里，避免重复。
然后把两两sum过一遍，遇到target - sum[i]在hashtable里存在的，把hashset里的这
2个key对应int[]都就试一次，去看每一组index是否有重复，没有，就排列好，塞
return的hashset里。
以前可以的，现在只能过小oj了。。。桑心。。。
求高人指教。 |
|
t**r
发帖数: 3428 | 9 class Solution {
public:
vector > fourSum(vector &num, int target) {
int n = num.size();
vector > ret;
sort(num.begin(), num.end());
for (int i = 0; i < n; ++i) {
if (i != 0 && num[i] == num[i - 1]) continue;
for (int j = n - 1; j > i; --j) {
if (j != n - 1 && num[j] == num[j + 1]) continue;
int L = i + 1, R = j - 1;
while (L < R) {
int sum ... 阅读全帖 |
|
|
c********t
发帖数: 5706 | 11 LC 4Sum O(n^3)是time complexity下届吗？我怎么觉得不是呢？ |
|
|
b******g
发帖数: 3616 | 13 今天正好复习到这题。顺手写了个k-sum的代码，过了LC的3sum和4sum的test。有兴趣帮
着找找有没有没发现的bug。我觉得理解了3sum的算法，并写过4sum以后，这个kSum其
实也就一个小变种，一个葫芦里的药了。由于代码不短，感觉面试的时候还是分成子程
序写比较好，即使时间来不及写完，至少思路能和面试官说清楚。
思路和排板好看点的代码写在自己的复习总结博客里了：
http://bangbingsyb.blogspot.com/2014/11/leetcode-4sum.html
代码：
class Solution {
public:
vector > fourSum(vector &num, int target) {
vector> allSol;
vector sol;
sort(num.begin(),num.end());
kSum(num, 0, num.size()-1, target, 4, sol, allSol);... 阅读全帖 |
|
c*********t
发帖数: 2921 | 14 看到最近有人问4sum的问题，
可是我想如果能对2sum ,3sum的问题弄透了，各种方法都研究一下，4sum应该就是一个
扩展，对吧。
我们能不能先列一下可以解决2sum的所有方法？假设数组中有重复的数。
有种方法是用hashtable,可是我发现有个问题，
比如给定数组 [ 1 2 3 4 5 6 7 8 9],求出之和为 10 (target)的两个数，
用hashtable,我们可以得到
1 9
2 8
3 7
4 6
5 5 <<<<<<<这里好像不对了，因为数组里只有一个5,这个问题该如何处理？
6 4
7 3
8 2
9 1
另外就是得出的组合有重复的，象 1 9, 其实和 9 1 是一回事，该怎么办？
还有哪些常用的方法来解决2sum问题的？
谢谢！ |
|
c********p
发帖数: 1969 | 15 呜呜，听起来像药不能听一样。。。
能帮我去看看4sum么？我以前写的和新写的4sum都过不了大oj了。以前的可以过的，我
复制粘贴的都过不去了。。。
leetcode聪明了。。。 |
|
A*******i
发帖数: 49 | 16 骑驴找马中，重新刷题，一天也刷不了几道~反正就是尽量挑些有趣的题刷刷，
leetcode上真是有些题看了就反胃，比如什么3sum，4sum，valid Sudoku啥的~原理就
是那么个东西，写起code来又麻烦又无聊
不知道大家都是怎么想的，比如一些题，就说3sum，4sum，就是2sum的思想反复用下，
大家还会去实打实写code吗？面试的时候要是面这种题是不是基本就可以对这个公司呵
呵了 |
|
z****e
发帖数: 54598 | 17 老姜，你按照这个顺序下去
你看看4sum的情况
会有多少种组合出现
比如
1-2，3-4，5－7，8-10
切三刀
你一个个要找过去好吧？
而且会出现，比如这里卖了2张，剩下1张，死活不匹配
但是
1-3，4-6，7-8，9-10
有三张，你这个时候要干掉之前的两张，然后match上这里的三张好吧？
所以其实你是从
全程，2对, 3对，4对，5对。。。。9对组合
这么多组合里面，找出一个sum恰好等于座位sum的这么一个过程
而且你在2sum的选择会影响到后面3sum, 4sum...等的具体数值
并不是一个独立的过程
这个复杂度很不低好吧？ |
|
|
a******g
发帖数: 13519 | 19 我跟我娃一起刷LeetCode，目标FLG，一同奋斗。现在我娃轻轻松松解4SUM。 |
|
i**********e
发帖数: 1145 | 20 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 a... 阅读全帖 |
|
q******8
发帖数: 848 | 21 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 | 22 n^3的算法还是很好想的，更好的就要动动脑筋了 |
|
l***i
发帖数: 1309 | 23 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 sa... 阅读全帖 |
|
d********w
发帖数: 363 | 24 如果改成 a+b = c+d，也是同样的复杂度吧
值, |
|
w***t
发帖数: 1474 | 25 万一2sum和target-2sum这两个sum包含同一个元素咋办。
sum1 = a + b;
sum2 = a + c;
target = a + a + b + c; 这样是错的把
值, |
|
r*****b
发帖数: 310 | 26 @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
发帖数: 663 | 28 这个可以在找到匹配的时候附加判断吧。
哈希表里头可以记录每个2sum的元素index,找到匹配的时候判断以下index是否重复就
是了. |
|
u**r
发帖数: 663 | 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]++; |
|
m*****k
发帖数: 731 | 30 here in your case, the n is the largest abs(S[i]),
while the N in the question is the S.length
, |
|
c********t
发帖数: 5706 | 31 真的吗？记得写过一个从N个数里找M个数，使和为<=S的最大值，复杂度为O(N*M*S).
求等于S应该一样吧。
, |
|
c********t
发帖数: 5706 | 32 回顾了一下，那个只要求出一组解，这题是要所有解，不一样。 |
|
t****a
发帖数: 1212 | 33 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) ; ... 阅读全帖 |
|
c********t
发帖数: 5706 | 34 10行太牛了，可惜读不懂pyton，能处理有重复的数情况吗？
比如 1,1,2，3,4 sum = 10.
)) |
|
c********t
发帖数: 5706 | 35 研究了一下你的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_... 阅读全帖 |
|
q******8
发帖数: 848 | 36 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 | 37 n^3的算法还是很好想的，更好的就要动动脑筋了 |
|
l***i
发帖数: 1309 | 38 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 sa... 阅读全帖 |
|
d********w
发帖数: 363 | 39 如果改成 a+b = c+d，也是同样的复杂度吧
值, |
|
w***t
发帖数: 1474 | 40 万一2sum和target-2sum这两个sum包含同一个元素咋办。
sum1 = a + b;
sum2 = a + c;
target = a + a + b + c; 这样是错的把
值, |
|
r*****b
发帖数: 310 | 41 @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
发帖数: 663 | 43 这个可以在找到匹配的时候附加判断吧。
哈希表里头可以记录每个2sum的元素index,找到匹配的时候判断以下index是否重复就
是了. |
|
u**r
发帖数: 663 | 44 有重复的话可以在哈希表里头记录重复次数阿，比如你给的例子中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]++; |
|
m*****k
发帖数: 731 | 45 here in your case, the n is the largest abs(S[i]),
while the N in the question is the S.length
, |
|
c********t
发帖数: 5706 | 46 真的吗？记得写过一个从N个数里找M个数，使和为<=S的最大值，复杂度为O(N*M*S).
求等于S应该一样吧。
, |
|
c********t
发帖数: 5706 | 47 回顾了一下，那个只要求出一组解，这题是要所有解，不一样。 |
|
t****a
发帖数: 1212 | 48 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) ; ... 阅读全帖 |
|
c********t
发帖数: 5706 | 49 10行太牛了，可惜读不懂pyton，能处理有重复的数情况吗？
比如 1,1,2，3,4 sum = 10.
)) |
|
c********t
发帖数: 5706 | 50 研究了一下你的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_... 阅读全帖 |
|
