C++ 优先算法 —— 四数之和（双指针）

题目：四数之和

1. 题目解析

2. 算法原理

Ⅰ. 暴力枚举

Ⅱ. 双指针算法

不漏的处理：

去重处理：

3. 代码实现

Ⅰ. 暴力枚举

Ⅱ. 双指针算法

题目：四数之和

1. 题目解析

题目截图：

这道题与三数之和（三数之和的解答）及两数之和（两数之和的解答）是很相似的，这道题目要求，也类似于三数之和，它这里的顺序上：

每个四元组的前后顺序可以任意
每个四元组中的数据顺序可以任意

这里target可以不同（target可以随意）。

2. 算法原理

这里也是同样有两种解法：

暴力枚举
双指针算法

Ⅰ. 暴力枚举

这里方法也是：排序+暴力枚举（从左往右）+去重

类比前面的三数之和：

//伪代码演示
for (int i = 0; i < n; i++) // 固定一个数afor (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 < rightj < ni < 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;}
};

提交记录：