C++ 优先算法 —— 四数之和（双指针）
目录
题目：四数之和
1. 题目解析
2. 算法原理
Ⅰ. 暴力枚举
Ⅱ. 双指针算法
不漏的处理：
去重处理：
3. 代码实现
Ⅰ. 暴力枚举
Ⅱ. 双指针算法
题目：四数之和
1. 题目解析
题目截图：
这道题与三数之和（三数之和的解答）及两数之和（两数之和的解答）是很相似的，这道题目要求，也类似于三数之和，它这里的顺序上：
- 每个四元组的前后顺序可以任意
- 每个四元组中的数据顺序可以任意
这里target可以不同（target可以随意）。
2. 算法原理
这里也是同样有两种解法：
- 暴力枚举
- 双指针算法
Ⅰ. 暴力枚举
这里方法也是：排序+暴力枚举（从左往右）+去重
类比前面的三数之和：
//伪代码演示
for (int i = 0; i < n; i++) // 固定一个数a
for (int j = i + 1; j < n; j++) //依次固定枚举第二个数
for (int k = j + 1; k < n; k++) //枚举第三个数
for(int z = k + 1; z < n; z++) //枚举第四个数
查找符合的四元组，去重...
这里套了四层for循环，时间复杂度就是O(N⁴)。（会出现超时问题）
Ⅱ. 双指针算法
这里同三数之和也是：排序+双指针+去重
这里就相当于划分成，固定第一个数，剩下的就是利用三数之和思想解决，三数之和中，也是要固定一个数（这里也就是第二个数），接着利用两数之和解决，也就是在剩下的区间内用双指针算法。
总结一下解决方法：
- 依次固定一个数a（从左往右固定a，固定枚举完这一个后，再换下一个）。
- 在a的后面的区间内，利用“三数之和”的思想，找到三个数，使这三个数的和等于target-a即可。
这里三数之和：
- 依次固定一个数b。
- 在b后面的区间内，利用双指针，找到两个数，使这两个数的和等于target-a-b即可。
通过上图可以看到需要套两次for循环加一个while，时间复杂度为O(N²)。
这里也是需要处理同三数之和的细节问题：
不漏的处理：
也就是确保所有符合条件的情况不漏掉，这里也是找到一种结果之后，不要停（两个指针不停），缩小区间（两指针都向内移动一步），继续寻找符合的情况。
去重处理：
这里需要考虑三个去重情况：
//伪代码演示
for (i = 0; i < n; i++) //固定数a
//利用三数之和
for (j = i + 1; j < n; j++) //固定数b
//双指针
while (left < right)
//处理数据，并去重
//这里去重同样注意越界问题的判断：
left < right
j < n
i < n接下来，实现代码。
3. 代码实现
题目链接：四数之和
Ⅰ. 暴力枚举
//这里时间复杂度:O(N⁴)
class Solution {
public:
vector<vector<int>> fourSum(vector<int>& nums, int target) {
// 1.排序
sort(nums.begin(), nums.end());
vector<vector<int>> ret; // 用来存储所有的四元组
// 2.暴力枚举
int n = nums.size();
int i, j, k, z;
for (i = 0; i < n;) // 固定一个数a
{
for (j = i + 1; j < n;) // 依次固定枚举第二个数
{
for (k = j + 1; k < n;) // 枚举第三个数
{
for (z = k + 1; z < n;) // 枚举第四个数
{
long long sum = (long)nums[i] + nums[j] + nums[k] + nums[z];
if (sum == target)
{
ret.push_back({nums[i], nums[j], nums[k], nums[z]});
}
// 去重z
++z;
while (z < n && nums[z] == nums[z - 1])
{
++z;
}
}
// 去重k
++k;
while (k < n && nums[k] == nums[k - 1])
{
++k;
}
}
// 去重j
++j;
while (j < n && nums[j] == nums[j - 1])
{
++j;
}
}
// 去重i
++i;
while (i < n && nums[i] == nums[i - 1])
{
++i;
}
}
return ret;
}
};提交记录（这里按理说会超时，时间复杂度:O(N⁴)，但这里通过了）：
Ⅱ. 双指针算法
//这里时间复杂度是O(N²)
class Solution {
public:
vector<vector<int>> fourSum(vector<int>& nums, int target) {
// 1.排序
sort(nums.begin(), nums.end());
vector<vector<int>> ret;
int n = nums.size();
// 2.利用双指针算法
int i, j;
for (i = 0; i < n;) //固定数a
{
//利用三数之和
for (j = i + 1; j < n;) //固定数b
{
//双指针
int left = j + 1;
int right = n - 1;
long long t = (long)target - nums[i] - nums[j]; //注意数据溢出问题，用long long解决
while (left < right)
{
int sum = nums[left] + nums[right];
if (sum > t)
{
--right;
}
else if (sum < t)
{
++left;
}
else
{
// 将获取的四元组尾插ret里
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;
}
};
提交记录：
制作不易,若有不足之处或出问题的地方，请各位大佬多多指教 ，感谢大家的阅读支持！！!
