一：题目解析

题目链接：18. 四数之和 - 力扣（LeetCode）

注：本题是在上题的基础上讲解的：专题一_双指针_三数之和-CSDN博客

解析：和三数之区别在于找四元组和为targe的数字而不是0

二：算法原理

①：暴力

根据上题可知，暴力的最快版本如下，会超时，时间复杂度高达O(N^4)

1：先对原数组排序
2：暴力枚举加判断
3：利用unordered_set去重

注：先排序的益处很大，但暴力仅仅用来规避了去重前的组内排序，所以对时间复杂度无提升

②：优秀

核心依旧是三数排序的思路，唯一改变的在于，我们在最左面固定一个值，此时在这个值的右区间进行三数之和的算法即可！

三：代码编写

class Solution {
public:vector<vector<int>> fourSum(vector<int>& nums, int target) {sort(nums.begin(),nums.end());//排序int n = nums.size();vector<vector<int>> v;//返回值for(int i = 0;i<n;)//最外层的值的固定 相较于三数之和的区别所在！！{for(int j=i+1;j<n;)//所有j也得从i+1开始！ 而三数之和是从0开始！{long long target2 = (long long)target-nums[i]-nums[j];//一定要long long类型 否则会溢出产生截断int left = j+1,right = n-1;//左指针从j+1 开始 右指针从最后一个元素开始while(left<right){int sum = nums[left]+nums[right];if(sum<target2) left++;else if(sum>target2) right--;else{v.push_back({nums[i],nums[j],nums[left],nums[right]});left++,right--;//双指针去重while(left<right && nums[left-1] == nums[left]) left++;while(left<right && nums[right+1] == nums[right]) right--;}}//j下标固定的元素去重j++;while(j<n && nums[j-1]==nums[j]) j++;}//i下标固定的元素去重i++;while(i<n && nums[i-1]==nums[i]) i++;}return v;}
};

解释：

1：因为四元组的和要为target，所以当到双指针的时候，双指针的和sum应该为:target-nums[i]-nums[j]!

2：一定要用long long类型，因为在四数之和问题中，target 和 nums[i]、nums[j] 可能是大整数，如果直接计算 target - nums[i] - nums[j]，可能会发生整数溢出！尤其当 nums[i] 和 nums[j] 是很大的负数时！

3：v进行push_back的时候，一定按照大小顺序进行push_bcak，如：nums[i],nums[j],nums[left],nums[right]