一、三数之和
1. 题目解析
三数之和【点击跳转】
题目的意思是给了我们一个数组nums，让我们找出三个下标不相同的数nums[i]，nums[j]，nums[k]，要求这三个数的和恰好等于，然后返回这三个数
注意： 返回的这个三元组不能是重复的
我们可以结合示例1的解释来看：
示例 1：
输入的数组是nums = [-1, 0, 1, 2, -1, -4]
解释：
第一种： n u m s [ 0 ] + n u m s [ 1 ] + n u m s [ 2 ] = ( − 1 ) + 0 + 1 = 0 第二种： n u m s [ 1 ] + n u m s [ 2 ] + n u m s [ 4 ] = 0 + 1 + ( − 1 ) = 0 第三种： n u m s [ 0 ] + n u m s [ 3 ] + n u m s [ 4 ] = ( − 1 ) + 2 + ( − 1 ) = 0 第一种：nums[0] + nums[1] + nums[2] = (-1) + 0 + 1 = 0 \\ 第二种：nums[1] + nums[2] + nums[4] = 0 + 1 + (-1) = 0 \\ 第三种：nums[0] + nums[3] + nums[4] = (-1) + 2 + (-1) = 0 第一种：nums[0]+nums[1]+nums[2]=(−1)+0+1=0第二种：nums[1]+nums[2]+nums[4]=0+1+(−1)=0第三种：nums[0]+nums[3]+nums[4]=(−1)+2+(−1)=0
可以看到第一种和第二种三元组里的元素都是 [-1, 0, 1] 忽略掉元素的顺序，他们的元素是一样的，所以是同一个三元组，所以这两个中任选一个就行了，另外，三元组中元素的顺序不重要，可以随意。所以输出的结果就是 [-1, 0, 1] 和 [-1, -1, 2]
2. 讲解算法原理
解法一：排序 + 暴力枚举 + 容器去重
我们可以将所有符合要求的三元组给枚举出来，然后直接利用set容器去重，但是在示例中可能会有很多种像示例一中的这种情况，所以我们可以先给数组排个序，另外，排完序后我们得到的三元组里面的元素顺序也会得到固定，这样也能够更好的让我们利用容器去重。
时间复杂度为：
O ( N 3 ) O(N^3) O(N3)
这里就直接给代码了，最后的提交结果肯定是超时的。
class Solution {
public:
vector<vector<int>> threeSum(vector<int>& nums) {
set<vector<int>> hash;
int n = nums.size();
vector<vector<int>> ret;
// 排序
sort(nums.begin(), nums.end());
// 暴力枚举
for(int i = 0; i < n; i++)
{
for(int j = i + 1; j < n; j++)
{
for(int k = j + 1; k < n; k++)
{
if(nums[i] + nums[j] + nums[k] == 0)
{
vector<int> tmp = {nums[i], nums[j], nums[k]};
// 容器去重 --> 排好序后元素位置固定, 相同的两个三元组第一个元素和最后一个元素肯定是相同的
if(hash.find(tmp) == hash.end())
{
ret.push_back(tmp);
hash.insert(tmp);
}
}
}
}
}
return ret;
}
};
解法二：排序 + 双指针
在暴力枚举的基础上进行的优化，前面做过一道和为s的两个数，如果想到这题，那么三数之和这道题就很好优化。
我们可以先固定一个数，假设这个数的下标是i，那么我们就在数组[i + 1, n - 1]（n表示这个数组的长度）这个区间做那个和为s的两个数，只不过这两个数的和是等于nums[i]的相反数。
注意：
1、跟和为s的两个数不同的是，这里不止有一种结果，所以利用双指针找到一组结果后，不要挺，需要缩小范围然后继续找，确保结果没有遗漏。
2、另外一个就是去重问题，首先想到的就是利用容器的特性去重。还有就是找到一种结果之后，可以让指针跳过重复的元素进行去重。
这里需要注意一下指针越界的问题，题目中给定的数组nums可能是 [0, 0, 0, 0, 0]，这种情况下指针会越界，所以在判断重复的元素时，left和right指针的关系是left < right，i 的话则需要小于数组的长度。
3. 代码编写
C++代码：
class Solution {
public:
vector<vector<int>> threeSum(vector<int>& nums) {
vector<vector<int>> ret;
int n = nums.size();
// 排序
sort(nums.begin(), nums.end());
// 利用双指针解决问题
for(int i = 0; i < n; )
{
// 小优化
if(nums[i] > 0) break;
// 定义左右双指针
int left = i + 1, right = n - 1, target = -nums[i];
while(left < right)
{
// 求和
int sum = nums[left] + nums[right];
if(sum < target) left++;
else if(sum > target) right--;
else
{
ret.push_back({nums[i], nums[left], nums[right]});
// 继续移动指针, 确保不漏
left++, right--;
// 去重left 和 right + 防止越界
while(left < right && nums[left] == nums[left - 1]) left++;
while(left < right && nums[right] == nums[right + 1]) right--;
}
}
// 去重固定的数 i + 防止越界
i++;
while(i < n && nums[i] == nums[i - 1]) i++;
}
// 返回结果
return ret;
}
};
C语言代码：
// 比较函数，用于qsort排序
int compare(const void* a, const void* b) {
return (*(int*)a - *(int*)b);
}
int** threeSum(int* nums, int numsSize, int* returnSize, int** returnColumnSizes) {
if (nums == NULL || numsSize < 3 || returnSize == NULL || returnColumnSizes == NULL) {
*returnSize = 0;
*returnColumnSizes = NULL;
return NULL;
}
qsort(nums, numsSize, sizeof(int), compare);
*returnSize = 0;
int capacity = numsSize / 3; // 合理的初始大小
int** ret = (int**)malloc(capacity * sizeof(int*));
*returnColumnSizes = (int*)malloc(capacity * sizeof(int));
for (int i = 0; i < numsSize - 2; ) {
if (nums[i] > 0) break;
int left = i + 1, right = numsSize - 1, target = -nums[i];
while (left < right) {
int sum = nums[left] + nums[right];
if (sum < target) {
left++;
} else if (sum > target) {
right--;
} else {
if (*returnSize >= capacity) {
capacity *= 2; // 动态扩展
int** temp = (int**)realloc(ret, capacity * sizeof(int*));
if (temp == NULL) {
free(ret);
free(*returnColumnSizes);
*returnSize = 0;
*returnColumnSizes = NULL;
return NULL;
}
ret = temp;
*returnColumnSizes = (int*)realloc(*returnColumnSizes, capacity * sizeof(int));
}
ret[*returnSize] = (int*)malloc(3 * sizeof(int));
ret[*returnSize][0] = nums[i];
ret[*returnSize][1] = nums[left];
ret[*returnSize][2] = nums[right];
(*returnColumnSizes)[*returnSize] = 3;
(*returnSize)++;
left++, right--;
while (left < right && nums[left] == nums[left - 1]) left++;
while (left < right && nums[right] == nums[right + 1]) right--;
}
}
i++;
while (i < numsSize && nums[i] == nums[i - 1]) i++;
}
ret = (int**)realloc(ret, *returnSize * sizeof(int*));
*returnColumnSizes = (int*)realloc(*returnColumnSizes, *returnSize * sizeof(int));
return ret;
}
Python代码：
class Solution:
def threeSum(self, nums: List[int]) -> List[List[int]]:
nums.sort() # 对数组进行排序
n = len(nums)
ret = [] # 用于存储结果的列表
for i in range(n):
# 小优化：如果当前数字大于0，则后续数字也大于0，不可能组成和为0的三元组
if nums[i] > 0:
break
# 去重：如果当前数字与前一个数字相同，跳过
if i > 0 and nums[i] == nums[i - 1]:
continue
# 定义左右双指针
left, right = i + 1, n - 1
target = -nums[i]
while left < right:
total = nums[left] + nums[right]
if total < target:
left += 1
elif total > target:
right -= 1
else:
# 找到一个满足条件的三元组
ret.append([nums[i], nums[left], nums[right]])
# 移动指针并去重
left += 1
while left < right and nums[left] == nums[left - 1]:
left += 1
right -= 1
while left < right and nums[right] == nums[right + 1]:
right -= 1
return ret
二、四数之和
1. 题目解析
四数之和【点击跳转】
和三数之和的题目意思一模一样，只不过是由三个数的和等于0变成了数组中四个数相加要等于目标值target，符合要求的四元组不能重复，结果不能有遗漏。
2. 讲解算法原理
你在逗我呢？三数之和都会了，四数之和还不会？不准往下看了，赶紧给我写代码去OvO。
解法一：排序 + 暴力枚举 + 容器去重
我们可以将所有符合要求的四元组给枚举出来，然后直接利用set容器去重，但是在示例中可能会有很多种像示例一中的这种情况，所以我们可以先给数组排个序，另外，排完序后我们得到的四元组里面的元素顺序也会得到固定，这样也能够更好的让我们利用容器去重。
时间复杂度为：
O ( N 4 ) O(N^4) O(N4)
这里就直接给代码了，最后的提交结果肯定是超时的。
class Solution {
public:
vector<vector<int>> fourSum(vector<int>& nums, int target) {
set<vector<int>> hash;
int n = nums.size();
vector<vector<int>> ret;
// 排序
sort(nums.begin(), nums.end());
// 暴力枚举
for(int i = 0; i < n; i++)
{
for(int j = i + 1; j < n; j++)
{
for(int k = j + 1; k < n; k++)
{
for(int y = k + 1; y < n; y++)
{
if((long long)nums[i] + nums[j] + nums[k] + nums[y] == target)
{
vector<int> tmp = {nums[i], nums[j], nums[k], nums[y]};
// 容器去重 --> 排好序后元素位置固定, 相同的两个三元组第一个元素和最后一个元素肯定是相同的
if(hash.find(tmp) == hash.end())
{
ret.push_back(tmp);
hash.insert(tmp);
}
}
}
}
}
}
return ret;
}
};
解法二：排序 + 双指针
其实就和三数之和的算法原理是一模一样的。只不过是由固定一个数变成了固定两个数，先固定一个数，然后对后面的数使用三数求和即可。
在暴力枚举的基础上进行的优化，前面做过一道和为s的两个数，如果想到这题，那么四数之和这道题就很好优化。
我们可以先固定一个数，假设这个数的下标是i，那么我们就在数组[i + 1, n - 1]（n表示这个数组的长度）这个区间做那个和为s的两个数，只不过这两个数的和是等于nums[i]的相反数。
注意：
1、跟和为s的两个数不同的是，这里不止有一种结果，所以利用双指针找到一组结果后，不要挺，需要缩小范围然后继续找，确保结果没有遗漏。
2、另外一个就是去重问题，首先想到的就是利用容器的特性去重。还有就是找到一种结果之后，可以让指针跳过重复的元素进行去重。
3. 代码编写
C++代码：
class Solution {
public:
vector<vector<int>> fourSum(vector<int>& nums, int target) {
vector<vector<int>> ret;
// 排序
sort(nums.begin(), nums.end());
int n = nums.size();
// if(n < 4) return ret;
for(int i = 0; i < n; ){ // 固定第一个数
for(int j = i + 1; j < n; ){ // 固定第二个数
// 左右双指针
int left = j + 1, right = n - 1;
long long rnum = (long long)target - nums[i] - nums[j];
while(left < right){
if(nums[left] + nums[right] > rnum) right--;
else if(nums[left] + nums[right] < rnum) left++;
else{
// 尾插
ret.push_back({nums[i], nums[j], nums[left++], nums[right--]});
// 对 left 和 right 进行去重处理
while(left < right && nums[left] == nums[left - 1]) left++;
while(left < right && nums[right] == nums[right + 1]) right--;
}
}
++j;
// 对 j 进行去重处理
while(j < n && nums[j] == nums[j - 1]) j++;
}
++i;
// 对 i 进行去重处理
while(i < n && nums[i] == nums[i - 1]) i++;
}
return ret;
}
};
C语言代码：
// 比较函数，用于qsort排序
int compare(const void* a, const void* b) {
return (*(int*)a - *(int*)b);
}
int** fourSum(int* nums, int numsSize, int target, int* returnSize, int** returnColumnSizes) {
// 排序
qsort(nums, numsSize, sizeof(int), compare);
// 初始化结果数组
*returnSize = 0;
int capacity = 100; // 初始容量，可根据需要调整
int** ret = (int**)malloc(capacity * sizeof(int*));
*returnColumnSizes = (int*)malloc(capacity * sizeof(int));
for (int i = 0; i < numsSize; ) {
for (int j = i + 1; j < numsSize; ) {
int left = j + 1, right = numsSize - 1;
long long rnum = (long long)target - nums[i] - nums[j];
while (left < right) {
long long sum = (long long)nums[left] + nums[right];
if (sum > rnum) {
right--;
} else if (sum < rnum) {
left++;
} else {
// 动态分配内存存储结果
if (*returnSize >= capacity) {
capacity *= 2;
ret = (int**)realloc(ret, capacity * sizeof(int*));
*returnColumnSizes = (int*)realloc(*returnColumnSizes, capacity * sizeof(int));
}
ret[*returnSize] = (int*)malloc(4 * sizeof(int));
ret[*returnSize][0] = nums[i];
ret[*returnSize][1] = nums[j];
ret[*returnSize][2] = nums[left];
ret[*returnSize][3] = nums[right];
(*returnColumnSizes)[*returnSize] = 4;
(*returnSize)++;
// 去重
left++;
while (left < right && nums[left] == nums[left - 1]) left++;
right--;
while (left < right && nums[right] == nums[right + 1]) right--;
}
}
// 去重固定第二个数
j++;
while (j < numsSize && nums[j] == nums[j - 1]) j++;
}
// 去重固定第一个数
i++;
while (i < numsSize && nums[i] == nums[i - 1]) i++;
}
// 重新分配内存以匹配实际结果数量
ret = (int**)realloc(ret, *returnSize * sizeof(int*));
*returnColumnSizes = (int*)realloc(*returnColumnSizes, *returnSize * sizeof(int));
return ret;
}
Python代码：
class Solution:
def fourSum(self, nums: List[int], target: int) -> List[List[int]]:
nums.sort() # 对数组进行排序
n = len(nums)
ret = [] # 用于存储结果的列表
for i in range(n): # 固定第一个数
# 去重处理：如果当前数字与前一个数字相同，跳过
if i > 0 and nums[i] == nums[i - 1]:
continue
for j in range(i + 1, n): # 固定第二个数
# 去重处理：如果当前数字与前一个数字相同，跳过
if j > i + 1 and nums[j] == nums[j - 1]:
continue
left, right = j + 1, n - 1 # 左右双指针
rnum = target - nums[i] - nums[j] # 剩余的目标值
while left < right:
total = nums[left] + nums[right]
if total > rnum:
right -= 1
elif total < rnum:
left += 1
else:
# 找到一个满足条件的四元组
ret.append([nums[i], nums[j], nums[left], nums[right]])
# 去重处理
while left < right and nums[left] == nums[left + 1]:
left += 1
while left < right and nums[right] == nums[right - 1]:
right -= 1
left += 1
right -= 1
return ret
