最近刷题发现k sum问题是非常经典的一种题型，看过别人代码后，总结求解k sum问题的通常思路。文章参考知乎leetcode之2sum丶3sum(closest)丶4sum算法总结。
1 2 sum
原题链接请点击这里。
Given an array of integers, return indices of the two numbers such that they add up to a specific target.
You may assume that each input would have exactly one solution, and you may not use the same element twice.
Example:
Given nums = [2, 7, 11, 15], target = 9,
Because nums[0] + nums[1] = 2 + 7 = 9,
return [0, 1].
翻译过来是说，给出一个整数数组和目标数，找到两个数使得他们的和等于目标数，返回这两个数的下标。每一个数只能使用一次。
这道题还是比较简单的，可以用暴力算法，两次循环来做出来。下面直接附上代码。
var twoSum = function(nums, target) {
var result = new Array();
for(var i=0;i<nums.length;i++){
for(var j=i+1;j<nums.length;j++){
if(nums[i] + nums[j] == target){
result[0] = i;
result[1] = j;
return result;
}
}
}
};
这道题大概是七八个月前刷的了，今天翻出来看发现和现在的代码风格都不太一样了。这种做法就是暴力比较，简单粗暴，容易想到。
2 3 sum
原题链接请点击这里。
Given an array S of n integers, are there elements a, b, c in S such that a + b + c = 0? Find all unique triplets in the array which gives the sum of zero.
Note:The solution set must not contain duplicate triplets.
For example, given array S = [-1, 0, 1, 2, -1, -4],
A solution set is:
[
[-1, 0, 1],
[-1, -1, 2]
]
翻译过来是说，给出一个整数数组，找到三个数使得这三个数的和为0，返回所有可能的这三个数，注意结果不能重复。
这道题可以看成先固定一个数，再对另外两个数利用2 sum的方法来求解。注意这里要去除重复值，这是一个不太好处理的点。
这里对于i来说，当nums[i]和nums[i-1]相等时，跳到下一次循环。对于left，当nums[left]和nums[left+1]相等时，left自增，找到后面的那个数，如果此时不等，需要left再增加一次。同理right也是一样，这里不再叙述。（表述的不太好，看下面这个图）。
left m m+1 m+2 m+3 m+4
数字 1 1 1 2 3
left为m时，判断m和m+1是否相等，相等left自增变为m+1
再比较m+1与m+2是否相等，还是相等left再自增变为m+2
再比较m+2与m+3是否相等，不等需要left再自增变为m+3，获取m+3的值
var threeSum = function(nums) {
nums.sort((a,b)=>a-b);//先对nums数组排序
var len = nums.length,left,right,res = new Array();
for(i=0;i<len-2;i++){
if(i > 0 && nums[i] == nums[i-1]){//判断当nums[i]==nums[i-1]时，跳出本次循环
continue;
}
left = i + 1;
right = len - 1;
while(left < right){
if(nums[i] + nums[left] + nums[right] < 0){//三个数的和小于0
left++;
}else if(nums[i] + nums[left] + nums[right] > 0){//三个数的和大于0
right--;
}else{//三个数的和等于0
var cur = new Array();
cur.push(nums[i]);
cur.push(nums[left]);
cur.push(nums[right]);
res.push(cur);
while(left < right && nums[left] == nums[left+1]){//判断当nums[left]==nums[left+1]时，left++
left++;
}
while(left < right && nums[right] == nums[right-1]){//判断当nums[right]==nums[right-1]时，right--
right--;
}
left++;//注意这里一定要在循环判断是不是有重复的数后 在改变 left right的值
right--;
}
}
}
return res;
};
3 3 sum closet
原题链接请点击这里。
Given an array S of n integers, find three integers in S such that the sum is closest to a given number, target. Return the sum of the three integers. You may assume that each input would have exactly one solution.
For example, given array S = {-1 2 1 -4}, and target = 1.
The sum that is closest to the target is 2. (-1 + 2 + 1 = 2).
翻译过来就是说，给出一个整数数组和目标数，找到三个整数使得这三个整数的和最接近目标数。假设只有一种解。
这道题是我在3 sum之前做的，当时写了一种时间复杂度O（n^3）的做法。三重循环暴力求值，结果时间上很慢很慢。参考了别人的代码后，找到了一种和3 sum类似的做法。
也是一开始要先判断i和i-1，如果nums[i]==nums[i-1]，要跳到下次循环。注意判断三个数和与目标数差的绝对值，如果小于记录的最小值，要更新。
var threeSumClosest = function(nums, target) {
nums.sort((a,b)=>a-b);
var left,right,i,len = nums.length,sum,min = Number.MAX_VALUE,res = 0;//res为三个数的和
for(i=0;i<len-2;i++){
if(i > 0 && nums[i] == nums[i-1]){//判断当nums[i]==nums[i-1]时，跳出本次循环
continue;
}
left = i + 1;
right = len - 1;
while(left < right){
sum = nums[i] + nums[left] + nums[right];
if(sum < target){//和小于目标数
if(target - sum < min){//目标数与那三个数的差小于记录的最小差，更新一下
min = target - sum;
res = sum;
}
left++;
}else if(sum > target){//和大于目标数
if(sum - target < min){//那三个数与目标数的差小于记录的最小差，更新一下
min = sum - target;
res = sum;
}
right--;
}else{//和等于目标数
return sum;
}
}
}
return res;
}
4 4 sum
原题链接请点击这里。
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.
**Note: **The solution set must not contain duplicate quadruplets.
For example, given array S = [1, 0, -1, 0, -2, 2], and target = 0.
A solution set is:
[
[-1, 0, 0, 1],
[-2, -1, 1, 2],
[-2, 0, 0, 2]
]
翻译过来就是说，给出一个整数数组和目标数，从中找到所有可能的4个数，使得这四个数的和等于目标数。注意不能有重复的情况。
这道题的做法，我还是依然采用了跟之前3 sum类似的做法，时间复杂度是O（n3），没有参考别人的O（n2）的做法，毕竟O（n^2）的做法不太好理解。
一开始要判断nums[i]和nums[i-1]，如果相等，就跳到下次循环。也要判断nums[j]和nums[j-1]，如果相等，跳到下次循环。然后比较四个数的和与目标数的大小，最后要注意去除nums[left]与nums[left++]，nums[right]与nums[right--]的重复值。
var fourSum = function(nums, target) {
nums.sort((a,b)=>a-b);
var left,right,len = nums.length,res = new Array(),i,j;
for(i=0;i<len-3;i++){
if(i > 0 && nums[i] == nums[i-1]){
continue;
}
for(j=i+1;j<len-2;j++){
if(j > i + 1 && nums[j] == nums[j-1]){
continue;
}
left = j + 1;
right = len - 1;
while(left < right){
if(nums[i] + nums[j] + nums[left] + nums[right] < target){
left++;
}else if(nums[i] + nums[j] + nums[left] + nums[right] > target){
right--;
}else{
var cur = new Array();
cur.push(nums[i]);
cur.push(nums[j]);
cur.push(nums[left]);
cur.push(nums[right]);
res.push(cur);
while(left < right && nums[left] == nums[left+1]){
left++;
}
while(left < right && nums[right] == nums[right-1]){
right--;
}
left++;
right--;
}
}
}
}
return res;
};
5 总结
k sum问题的时间复杂度一般是O（n^k-1），不排除有一些很好的但是不容易想到的做法。注意去重的代码部分，对于k sum问题是通用的。希望对各位刷题的童鞋有所帮助。
码字不易，请尊重作者版权，转载注明出处。
By BeLLESS 2017.7.15 20:45
