f*****u
发帖数: 308 | 1 k-sum: 给定一个数组A, A中无重复数字,且都是正整数,k,target是某两个给定数,求A
中所有可能的k个数,其和等于target.也就是2sum,3sum,4sum等等的通解. | l******i
发帖数: 194 | | h**d
发帖数: 630 | 3 sort然后dfs吧
A
【在 f*****u 的大作中提到】
: k-sum: 给定一个数组A, A中无重复数字,且都是正整数,k,target是某两个给定数,求A
: 中所有可能的k个数,其和等于target.也就是2sum,3sum,4sum等等的通解.
| b******g
发帖数: 3616 | 4 感觉应该递归做。
k sum时，遍历每个A[i]：需要在A[i+1:n-1]中解 k-1 sum问题, target = target - A
[i]。一直递归到2 sum的时候算是base case，直接解。
网上有文章讲这个的。
http://tech-wonderland.net/blog/summary-of-ksum-problems.html
【在 l******i 的大作中提到】
: 求标准答案～是recursive呢还是咋整～
| l******i
发帖数: 194 | 5 但是也有大神告诉我是用n/2的map做！
A
【在 b******g 的大作中提到】
: 感觉应该递归做。
: k sum时，遍历每个A[i]：需要在A[i+1:n-1]中解 k-1 sum问题, target = target - A
: [i]。一直递归到2 sum的时候算是base case，直接解。
: 网上有文章讲这个的。
: http://tech-wonderland.net/blog/summary-of-ksum-problems.html
| b******g
发帖数: 3616 | 6 我记得有这种解法的，但不是对任何k都有效。似乎k必须是2^y才行。
【在 l******i 的大作中提到】
: 但是也有大神告诉我是用n/2的map做！
:
: A
| s******n
发帖数: 226 | 7 天 这是怎么了 难道不是subset sum吗，还不重复.... | j**********3
发帖数: 3211 | | b******g
发帖数: 3616 | 9 今天正好复习到这题。顺手写了个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);
return allSol;
}
void kSum(vector &num, int start, int end, int target, int k,
vector &sol, vector> &allSol) {
if(k<=0) return;
if(k==1) {
for(int i=start; i<=end; i++) {
if(num[i]==target) {
sol.push_back(target);
allSol.push_back(sol);
sol.pop_back();
return;
}
}
}
if(k==2) {
twoSum(num, start, end, target, sol, allSol);
return;
}
for(int i=start; i<=end-k+1; i++) {
if(i>start && num[i]==num[i-1]) continue;
sol.push_back(num[i]);
kSum(num, i+1, end, target-num[i], k-1, sol, allSol);
sol.pop_back();
}
}
void twoSum(vector &num, int start, int end, int target, vector
> &sol, vector> &allSol) {
while(start
int sum = num[start]+num[end];
if(sum==target) {
sol.push_back(num[start]);
sol.push_back(num[end]);
allSol.push_back(sol);
sol.pop_back();
sol.pop_back();
start++;
end--;
while(num[start]==num[start-1]) start++;
while(num[end]==num[end+1]) end--;
}
else if(sum
start++;
else
end--;
}
}
}; | y*********i
发帖数: 19 | 10 这个问题如果不用特殊数据结构的话，貌似好几十年前就研究过了
k为偶数，k/2个数为一组（4sum时就是算出每个pair的和，共n^2个），排序，然后two
pointe前后往中间走，复杂度n^(k/2)logn
k为奇数，需要多一重循环，n^(k/2） | z***m
发帖数: 1602 | 11 k是给定，必须满足。subset sum没有要求一定要k个数
【在 s******n 的大作中提到】
: 天 这是怎么了 难道不是subset sum吗，还不重复....
|
|
