自律是普通人最大的武器
🏠 博客主页：虚无的纽扣
📦 作者仓库：github | gitee
引言
最近因为一些原因拖更了很长时间的算法文章，后续我会慢慢补回来，今天要讲解的是三数之和、四数之和。
三数之和
接下来我们先来解析一下这个题目，该题目的要求是要求我们找到三个数，并且这三个数的和为零，通过题目要求我们可以发现：一个三元组除了在全零的情况下，一定至少要存在一个数为负数，不然相加无法得到零，并且该数组为递增数组。根据这个发现，接下来我们来讲解这道题的解题思路。
首先根据我们上面的发现，我们可以先将下标为0的数固定下来，记作con，然后让left等于1，right等于n-1，当它们三个相加之和大于0时，right就减减，当相加之和小于0时，left就加加。而当它们三个的和等于0时就记录下结果，并且很明显如果left或right下一次移动时的数和当前数字一样，那么结果还是0，就没必要重复计算，所以我们直接进行判断并且跳过所有的重复数字，直接进行运算，就可以节省一点时间。当left大于或等于right后，第一次循环结束，将让con加加，进行第二轮循环，直到con对应的位置大于零为止。
通过上面的讲解相信大家应该大致理解了一点思路，接下来贴出源代码，结合着思路和代码很容易就能理解这道题
class Solution {
public:
vector<vector<int>> threeSum(vector<int>& nums) {
sort(nums.begin(), nums.end());
int con = 0;
vector<vector<int>> ve;
while (nums.size() - con > 2 && nums[con] <= 0)
{
int left = con + 1, right = nums.size() - 1;
while (left < right)
{
if (nums[left] + nums[right] + nums[con] > 0)
{
right--;
}
else if (nums[left] + nums[right] + nums[con] < 0)
{
left++;
}
else
{
ve.push_back({nums[left++], nums[right--], nums[con]});
while (left < right && nums[left] == nums[left - 1])
left++;
while (left < right && nums[right] == nums[right + 1])
right--;
}
}
con++;
while (con < nums.size() && nums[con] == nums[con - 1])
{
con++;
}
}
return ve;
}
};四数之和
四数之和是三数之和的超级加强版，写起来特别的恶心和复杂，题目解析就不做了，和上面的三数之和差不多，我们直接进入解析
首先该数组并不是有序的，我们先用排序将它变成有序，然后我们还是一样先把数组前面的数固定，不一样的是这次要固定两个，并且如果数组的最小值加数组最大的三个值就已经大于目标值，就代表该数组无论如何都找不到结果，直接返回空。
我们要写一个深度超级深的大循环，第一层循环跟三数之和一样，固定最小值，设为i，如果i、i+1、i+2、i+3的值加起来已经大于目标值，则说明不管怎么移动都会比目标值大，没有意义，直接break。而如果i、n-1、n-2、n-3的值加起来小于目标值，也没有意义，不管怎么移动都不可能大于或等于目标值，所以直接进入下一轮循环。
固定下来i值后，我们再固定下来j值等于i+1，接着重复上一级循环的两个判断，如果都通过了，就设left和right，接下来的写法就不用我说了，直接用三数之和的解法来写就行。需要注意的是，因为数据过多，可能会导致四数之和超出int的范围，所以最好将记录结果的值设为long或者long long类型，在进行计算时最好也进行一次强转。
这题究极臃肿，究极复杂，究极恶心，并没有任何价值，大家大概理解就行，下附源代码
class Solution {
public:
vector<vector<int>> fourSum(vector<int>& nums, int target) {
vector<vector<int>> quadruplets;
if (nums.size() < 4) {
return quadruplets;
}
sort(nums.begin(), nums.end());
int length = nums.size();
for (int i = 0; i < length - 3; i++) {
if (i > 0 && nums[i] == nums[i - 1]) {
continue;
}
if ((long) nums[i] + nums[i + 1] + nums[i + 2] + nums[i + 3] > target) {
break;
}
if ((long) nums[i] + nums[length - 3] + nums[length - 2] + nums[length - 1] < target) {
continue;
}
for (int j = i + 1; j < length - 2; j++) {
if (j > i + 1 && nums[j] == nums[j - 1]) {
continue;
}
if ((long) nums[i] + nums[j] + nums[j + 1] + nums[j + 2] > target) {
break;
}
if ((long) nums[i] + nums[j] + nums[length - 2] + nums[length - 1] < target) {
continue;
}
int left = j + 1, right = length - 1;
while (left < right) {
long sum = (long) nums[i] + nums[j] + nums[left] + nums[right];
if (sum == target) {
quadruplets.push_back({nums[i], nums[j], nums[left], nums[right]});
while (left < right && nums[left] == nums[left + 1]) {
left++;
}
left++;
while (left < right && nums[right] == nums[right - 1]) {
right--;
}
right--;
} else if (sum < target) {
left++;
} else {
right--;
}
}
}
}
return quadruplets;
}
};
转载自 CSDN-专业IT技术社区
原文链接：https://blog.csdn.net/button__c/article/details/167916064
