文章目录
- 一、题目
- 二、解法
- 三、完整代码
所有的LeetCode题解索引，可以看这篇文章——【算法和数据结构】LeetCode题解。
一、题目
二、解法
思路分析：本题的解法借助了【算法与数据结构】15、LeetCode三数之和的算法思想。首先我们进行排序，然后检查输入数据的合法性，小于四个元素直接退出，明显不存在四元组的情况也直接退出。最外面的循环从0开始，然后我们将找 四元组和为target 的任务分解成找三元组和为target_three的任务，接下来就是三元组和为目标值的算法。
程序如下：
class Solution {
public:
vector<vector<int>> fourSum(vector<int>& nums, int target_four) {
sort(nums.begin(), nums.end()); // 升序排列
//my_print1(nums, "排序后数组");
vector<vector<int>> result;
int n = nums.size();
// 检查合法性
if (n < 4) return result; // 元素小于四个 返回
// Target小于最小四元组的和或者大于最大四元组的和 返回
// 需要强转成double类型，否则int会溢出, \为代码换行符，表示上下两行属于同一行
if ((double)target_four < (double)nums[0] + (double)nums[1] + (double)nums[2] + (double)nums[3] || \
(double)target_four >(double)nums[n - 4] + (double)nums[n - 3] + (double)nums[n - 2] + (double)nums[n - 1]) \
return result;
for (int j = 0; j < n; ++j) {
if (j > 0 && nums[j] == nums[j - 1]) continue; // j去重
int target_three = target_four - nums[j]; // 将找 四元组和为target 的任务 分解成 找三元组和为target_three
for (int i = j+1; i < n; ++i) {
if (i > j+1 && nums[i] == nums[i - 1]) continue; // i去重
int right = n - 1; // 最右端
int temp = -nums[i] + target_three;
for (int left = i + 1; left < n; ++left) {
if (left > i + 1 && nums[left] == nums[left - 1]) continue; // left去重
while (left < right && nums[left] + nums[right] > temp) {
--right;
// 三者之和大于0，right收缩，一直收缩到小于等于0或者left=right为止
}
if (left == right) break; // 不存在三元组，因此break。
if (nums[left] + nums[right] == temp) {
result.push_back({ nums[j], nums[i], nums[left], nums[right] });
}
}
}
}
return result;
}
};
复杂度分析：
- 时间复杂度： O ( n 3 ) O(n^3) O(n3)，在三数之和的基础上加上一层循环，因此是 O ( n 3 ) O(n^3) O(n3)。
- 空间复杂度： O ( 1 ) O(1) O(1)。
三、完整代码
测试代码如下，特别需要注意两个极端的数组，也是题目的边界条件，判断合法性的语句不能用int，int类型在相加是会溢出，这里我强制转换成double类型，能够存储的范围更大。
# include <iostream>
# include <string>
# include <vector>
# include <algorithm>
using namespace std;
void GeneratorVector(int arr[], int arr_len, vector<int>& v) {
for (int i = 0; i < arr_len; i++) {
v.push_back(arr[i]);
}
}
void my_print1(vector<int>& v, string str) {
cout << str << endl;
for (vector<int>::iterator it = v.begin(); it < v.end(); ++it) {
cout << *it << ' ';
}
cout << endl;
}
void my_print2(vector<vector<int>>& v, string str) {
cout << str << endl;
for (vector<vector<int>>::iterator vit = v.begin(); vit < v.end(); ++vit) {
for (vector<int>::iterator it = (*vit).begin(); it < (*vit).end(); ++it) {
cout << *it << ' ';
}
cout << endl;
}
}
class Solution {
public:
vector<vector<int>> fourSum(vector<int>& nums, int target_four) {
sort(nums.begin(), nums.end()); // 升序排列
//my_print1(nums, "排序后数组");
vector<vector<int>> result;
int n = nums.size();
// 检查合法性
if (n < 4) return result; // 元素小于四个 返回
// Target小于最小四元组的和或者大于最大四元组的和 返回
// 需要强转成double类型，否则int会溢出, \为代码换行符，表示上下两行属于同一行
if ((double)target_four < (double)nums[0] + (double)nums[1] + (double)nums[2] + (double)nums[3] || \
(double)target_four >(double)nums[n - 4] + (double)nums[n - 3] + (double)nums[n - 2] + (double)nums[n - 1]) \
return result;
for (int j = 0; j < n; ++j) {
if (j > 0 && nums[j] == nums[j - 1]) continue; // j去重
int target_three = target_four - nums[j]; // 将找 四元组和为target 的任务 分解成 找三元组和为target_three
for (int i = j+1; i < n; ++i) {
if (i > j+1 && nums[i] == nums[i - 1]) continue; // i去重
int right = n - 1; // 最右端
int temp = -nums[i] + target_three;
for (int left = i + 1; left < n; ++left) {
if (left > i + 1 && nums[left] == nums[left - 1]) continue; // left去重
while (left < right && nums[left] + nums[right] > temp) {
--right;
// 三者之和大于0，right收缩，一直收缩到小于等于0或者left=right为止
}
if (left == right) break; // 不存在三元组，因此break。
if (nums[left] + nums[right] == temp) {
result.push_back({ nums[j], nums[i], nums[left], nums[right] });
}
}
}
}
return result;
}
};
int main()
{
// 测试案例
//int arr[] = { 1,0,-1,0,-2,2 };
//int target = 0;
//int arr[] = { 2, 2,2,2,2 };
//int target = 8;
//int arr[] = { 1,-2,-5,-4,-3,3,3,5 };
//int target = -11;
//int arr[] = { 1000000000,1000000000,1000000000,1000000000 };
//int target = 0;
int arr[] = { -1000000000,-1000000000,1000000000,-1000000000,-1000000000 };
int target = 294967296;
int arr_len = sizeof(arr) / sizeof(int);
vector<int> nums;
GeneratorVector(arr, arr_len, nums);
my_print1(nums, "目标数组：");
Solution s1;
vector<vector<int>> result = s1.fourSum(nums, target);
my_print2(result, "结果：");
system("pause");
return 0;
}
end
