一：題目解析

題目鏈接：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]