18. 四數(shù)之和

給你一個(gè)由?n?個(gè)整數(shù)組成的數(shù)組?nums?，和一個(gè)目標(biāo)值?target?。請(qǐng)你找出并返回滿(mǎn)足下述全部條件且不重復(fù)的四元組?[nums[a], nums[b], nums[c], nums[d]]?（若兩個(gè)四元組元素一一對(duì)應(yīng)，則認(rèn)為兩個(gè)四元組重復(fù)）：

• 0 <= a, b, c, d?< n

• a、b、c?和?d?互不相同

• nums[a] + nums[b] + nums[c] + nums[d] == target

你可以按?任意順序?返回答案 。

?

示例 1：

輸入：nums = [1,0,-1,0,-2,2], target = 0輸出：[[-2,-1,1,2],[-2,0,0,2],[-1,0,0,1]]

示例 2：

輸入：nums = [2,2,2,2,2], target = 8輸出：[[2,2,2,2]]

?

提示：

• 1 <= nums.length <= 200

• -109?<= nums[i] <= 109

• -109?<= target <= 109

第一種對(duì)法：

雙指針?lè)?，時(shí)間復(fù)雜度O(n^3)

class?Solution?{

public:

????vector<vector<int>>?fourSum(vector<int>&?nums,?int?target)?{

????????vector<vector<int>>ans;

????????sort(nums.begin(),nums.end());

????????for(int?i?=?0;i<nums.size();i++){

????????????if(nums[i]>=0&&nums[i]>target)break;

????????????if(i>0&&nums[i]==nums[i-1])continue;

????????????for(int?j?=?i+1;j<nums.size();j++){

????????????????if(nums[j]+nums[i]>target&&nums[j]+nums[i]>=0)break;

????????????????if(j>i+1&&nums[j]==nums[j-1])continue;

????????????????int?left,right;

????????????????left?=?j+1,right=nums.size()-1;

????????????????while(left<right){

????????????????????if((long)nums[i]+nums[j]+nums[left]+nums[right]>target){

????????????????????????right--;

????????????????????}else?if((long)nums[i]+nums[j]+nums[left]+nums[right]<target){

????????????????????????left++;

????????????????????}else{

????????????????????????ans.push_back(vector<int>{nums[i],nums[j],nums[left],nums[right]});

????????????????????????while(left<right&&nums[left]==nums[left+1])left++;

????????????????????????while(left<right&&nums[right]==nums[right-1])right--;

????????????????????????left++,right--;

????????????????????}

????????????????}

????????????}

????????}

????????return?ans;

????}

};

思路：沿用了三數(shù)之和的思路，在多加了一層循環(huán)，重點(diǎn)是去重和剪枝的細(xì)節(jié)

剪枝：

1. 第一層剪枝：當(dāng)nums[i]>target時(shí)若nums[i]大于或等于0就說(shuō)明后面的數(shù)都是正數(shù)已經(jīng)無(wú)法等于target

2. 第二層剪枝：當(dāng)nums[i]+nums[j]>target時(shí)同上

3. 去重細(xì)節(jié)與三數(shù)之和相同