题目
给你一个由 n 个整数组成的数组 nums ，和一个目标值 target 。请你找出并返回满足下述全部条件且不重复的四元组 [nums[a], nums[b], nums[c], nums[d]] ：
- 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]]
解题
四数之和，和15.三数之和是一个思路，都是使用双指针法, 基本解法就是在15.三数之和 的基础上再套一层for循环。
python写法
class Solution: def fourSum(self, nums: List[int], target: int) -> List[List[int]]: n = len(nums) if n<4: return [] nums.sort() res = [] for i in range(n): if i>0 and nums[i]==nums[i-1]: continue for j in range(i+1,n-2): # 新添加的循环 if j>i+1 and nums[j]==nums[j-1]: continue L = j+1 R = n-1 while L<R: s = nums[i]+nums[j]+nums[L]+nums[R]-target if s==0: res.append([nums[i],nums[j],nums[L],nums[R]]) while L<R and nums[L]==nums[L+1]: L+=1 while L<R and nums[R]==nums[R-1]: R-=1 L+=1 R-=1 if s<0: L+=1 if s>0: R-=1 return res
c++写法
class Solution { public: vector<vector<int>> fourSum(vector<int>& nums, int target) { int n=nums.size(); if(n<4) return {}; sort(nums.begin(),nums.end()); vector<vector<int>> res; for(int i=0;i<n;i++){ if(i>0&&nums[i]==nums[i-1]) continue; for(int j=i+1;j<n;j++){ if(j>i+1&&nums[j]==nums[j-1]) continue; int L=j+1,R=n-1; while(L<R){ if(nums[i]+nums[j]-target==-nums[L]-nums[R]){ res.push_back({nums[i],nums[j],nums[L],nums[R]}); while(L<R&&nums[L]==nums[L+1]) L++; while(L<R&&nums[R]==nums[R-1]) R--; L++; R--; } else if(nums[i]+nums[j]-target<-nums[L]-nums[R]) L++; else R--; } } } return res; } };
因为官方增加了一个新的用例
{1000000000，1000000000，1000000000，1000000000} 0
导致了代码出现溢出错误，是因为int的只能到表示[-2147483648,2147483647]，所以在判断
num[a]+num[b]+num[c]+num[d]
时会溢出。因为不想对代码进行大改了所以将表达式调整为
nums[a]+nums[b]-target<-(nums[c]+nums[d])
这样子就不会溢出了。当然也可以使用long long int来表示数值，这样也不会溢出。(边界处理很重要，但学习
双指针的思想更重要~)
写法二：
由于判断表达式太长，可以使用宏定义精简一点。
#define compare(symbol) nums[i]+nums[j]-target symbol -nums[L]-nums[R] class Solution { public: vector<vector<int>> fourSum(vector<int>& nums, int target) { vector<vector<int>> res; int n=nums.size(); sort(nums.begin(),nums.end()); for(int i=0;i<n;i++){ if(i>0&&nums[i]==nums[i-1]) continue; for(int j=i+1;j<n;j++){ if(j>i+1&&nums[j]==nums[j-1]) continue; int L=j+1; int R=n-1; while(L<R){ if(compare(==)){ res.push_back({nums[i],nums[j],nums[L],nums[R]}); while(L<R&&nums[L]==nums[L+1]) L++; while(L<R&&nums[R]==nums[R-1]) R--; L++; R--; } else if(compare(<)){ L++; } else{ R--; } } } } return res; } };
java写法
由于存在很大的数，因此转long
class Solution { public List<List<Integer>> fourSum(int[] nums, int target) { List<List<Integer>> res=new LinkedList<>(); int n=nums.length; Arrays.sort(nums); for(int i=0;i<n;i++){ if(i>0&&nums[i]==nums[i-1]) continue; for(int j=i+1;j<n;j++){ if(j>i+1&&nums[j]==nums[j-1]) continue; int L=j+1,R=n-1; while(L<R){ if((long)nums[i]+nums[j]-target==-nums[L]-nums[R]){ res.add(Arrays.asList(nums[i],nums[j],nums[L],nums[R])); while(L<R&&nums[L]==nums[L+1]) L++; while(L<R&&nums[R]==nums[R-1]) R--; L++; R--; }else if(nums[i]+nums[j]<target-nums[L]-nums[R]){ L++; }else{ R--; } } } } return res; } }
