K数之和
题目描述：给你任意N个数组成的数组，给定一个目标值target，要求找出K个数，使得这K个数的总和为target，要求输出所有符合该条件的K位数的组合，组合不得重复
（以K=4为例）
输入：nums = [1,0,-1,0,-2,2], target = 0 输出：[[-2,-1,1,2],[-2,0,0,2],[-1,0,0,1]]
如题所示，在明知K的情况，我们可以设置K层循环，对每种可能n1...nk，使得n1+..nk==target时保存，但很明显，K不明确的情况下我们没法设置循环，换言之，这种办法太冗余，而且针对题目的数据规模要求，这种暴力枚举必定超时
那么可以借助递归来完成此题，我们知道，解决规模为N的问题，需要借助N-1规模问题的解决方案，那么，假设我们需要四个数相加为target，假定一个值已经确定为i，那么我们只需要解决 三个数相加为target-i的问题，而后者与前者的解决方法是同态的，因此，我们可以编写函数进行递归
对于该问题，我们可以先进行排序，使得查找过程尽可能的短，排序后我们主要可以省去的是：当查找某个target时，使用双指针，分别指向最大最小值（严格来说应该是起始值），当发现和不等于target时，就令一方的指针移动，原理可以参考“前N大的数”，这样可以加快寻找的进度
从简单的方法说起，上述的方法可以直接实现，但重点是如何把“结果”进行储存？，我们应该借助一个vector数组来存放答案，每进入一层前就先放进去，然后进行所谓的递归，无论递归的结果最后找到没有，我们都应该把这一层放进去的东西popback掉（没找到得退出来，找到了也得退出来继续找），当我们不断pushback后，到一个临界条件，发现target此时为0，说明最后一个数已经找到了，我们就把这个vector数组放入一个vecotr
简单版实现代码如下
void ksum(int k, int start, int target, int num[])//K为几位数字 start为开始位置
{
if (k == 0)
{
if (target == 0)
{
ans.push_back(tmp);
}
return;
}
else
{
for (int i = start;i <=len-k;i++) //如果需要找四位数，那么我们固定一位后，至少在
//剩下的数组中有三位数能够让我们查找
//不然固定一位后，剩下的都不足三位，又怎么能凑齐四位？
//K个数同理。
{
if (i > start && num[i] == num[i - 1])continue;
tmp.push_back(num[i]);
ksum(k - 1, i + 1, target - num[i], num);
tmp.pop_back();
}
}
}
注意这里的if (i > start && num[i] == num[i - 1])continue;为什么要这么做，答案是去重，发现网上对该去重原理讲的不是特别深入，在此作详细解释：以 -2 -1 -1 0 1 为例，当我们固定了第一个-1，此时我们需要在-1 0 1中寻找 target-（-1），但当我们固定了第二个-1，此时我们需要在 0 1 中寻找 target -（-1）,仔细观察，我们发现，如果0 1 是-1 0 1的子集，寻找全集的过程中其实就已经寻找过子集了！这也就是为什么不加该判断条件会重复的原因！假设我们需要的目标值为1，-1 0 1的答案是 0 1,0 1的答案也是0 1，但这两个搜索的过程固定的是两个不同位置的-1，但我们每搜索一次，就会丢进一个元素，这也就是会重复的来源，讲最明白一点， 子集中能找到，全集上肯定能找得到，但我们必定是越访问越短，全集已经找到了，子集就不必寻找了，重点是因为搜寻值相同。
运行结果如下：（K==4,target=0,num.length=6的情况下为例）
当然这个简单版只是解决较少数字，放在LeetCode上必定会超时，我们发现，当找到最后一个数的时候，我们可以直接进行判定了，不必再递归一次，因此我们直接写入n==2的情况
进阶版代码如下：
void kksum(int k, int start, int target, int num[])
{
if (k > 2)
{
for (int i = start;i <= len - k;i++)
{
if (i > start && num[i] == num[i - 1])continue;
else
{
tmp.push_back(num[i]);
kksum(k - 1, i + 1, target - num[i], num);
tmp.pop_back();
}
}
}
else if(k==2)
{
int left = start,right=len-1;
while (left < right)
{
if (num[left] + num[right] == target)
{
tmp.push_back(num[left]);
tmp.push_back(num[right]);
ans.push_back(tmp);
tmp.pop_back();
tmp.pop_back();
while (left < right && num[left] == num[left + 1])left++;
while (left < right && num[right] == num[right - 1])right--;
left++;
right++;
}
else if (num[left] + num[right] > target)
{
do
{
right--;
} while (left
值得注意的是，当我们的结果与target不同时，指针不必移动后就马上结束，我们判断下，指针移动后指向的值是否相同，如果相同，即便是下一次while判断，结果也是一样的，所以我们要两个do while循环，使得left和right指针不断移动，直到指向的值不等于先前指向的值
其二，我们找到结果后，不只移动一方，如果只移动一方，由于数组有序，两个加数必定有一个数比之前的小或者大，无论怎么单向移都是不符合target的，那么我们同时移动即可，这样就保证一个变大一个变小，当然你单方面移动也可以，多进行一次while而已，有n个答案就要多进行n个while。
原理已经明确，将代码改装进leetcode,通过了，但是效率还是有点低
当然我们既然已经知道了K=4,可以直接写四层for或者while循环
代码如下图所示：
vector> fourSum(vector& nums, int target) {
vector>ans;
if (nums.size() < 4)return ans;
sort(nums.begin(), nums.end());
int len = nums.size();
for (int i = 0;i <= len - 4;i++)
{
if (i > 0 && nums[i] == nums[i - 1])continue;
tmp.push_back(nums[i]);
for (int j = i + 1;j <= len - 3;j++)
{
if (j > i+1 && nums[j] == nums[j - 1])continue;
tmp.push_back(nums[j]);
int left = j + 1, right = len - 1;
while (left < right)
{
if (nums[left] + nums[right] == (target-nums[i]-nums[j]))
{
tmp.push_back(nums[left]);
tmp.push_back(nums[right]);
ans.push_back(tmp);
tmp.pop_back();
tmp.pop_back();
while (left < right && nums[left] == nums[left + 1])left++;
while (left < right && nums[right] == nums[right - 1])right--;
left++;
right--;
}
else if (nums[left] + nums[right] > (target - nums[i] - nums[j]))
{
do
{
right--;
} while (left < right && nums[right] == nums[right + 1]);
}
else if (nums[left] + nums[right] < (target - nums[i] - nums[j]))
{
do
{
left++;
} while (left < right && nums[left] == nums[left - 1]);
}
}
tmp.pop_back();
}
tmp.pop_back();
}
return ans;
这样子在空间上能更加开阔一点，无需再一步步进入函数，提交结果如下：
优化部分
由于数组有序，所以一些不必要的判断和递归可以直接省去，例如本题，我们需要一个固定值，但不是每一个数都可以当这个固定值的，假设这个数是固定值，那么就还要再选三个数，如果我们将这个数和前三位最大的数相加，仍然小于target，那么就可以直接continue到下一个i了，因为连最大的三位都没办法把这个数拉到target，更何况比这些数小的数，相反而言，如果target被平均分成了k份，连这个固定值都大于这个平均值了，更何况后面比固定值大的，加起来肯定也会大于target的因此有以下两个优化
1.当取K个数满足target时，若当前值与前K-1大的数相加仍然小于target，直接continue开启下一轮
2.当当前值小于target的平均K值时，说明该数往后相加必然大于target，直接break掉此层循环。
代码部分略
优化后的结果：（递归版）
(for循环版)
for循环进行优化后就是这个解法下几乎最优的版本了，当然还可以做的更细致一点，对异常行为直接return，能够提高程序运行效率
希望这篇文章能帮助到您，文章中有不妥当、错误的地方，还请您不吝赐教！
欢迎分享，转载请注明来源：内存溢出
微信扫一扫
支付宝扫一扫
评论列表（0条）