目录
题目：四数之和
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;}
};
提交记录：
制作不易,若有不足之处或出问题的地方，请各位大佬多多指教 ，感谢大家的阅读支持！！!
