例如：给出的数组 S = {1 0 -1 0 -2 2}, 目标值 = 0.↵↵ 给出的解集应该是：↵ (-1, 0, 0, 1)↵ (-2, -1, 1, 2)↵ (-2, 0, 0, 2)
Note:
For example, given array S = {1 0 -1 0 -2 2}, and target = 0.↵↵ A solution set is:↵ (-1, 0, 0, 1)↵ (-2, -1, 1, 2)↵ (-2, 0, 0, 2)
继续套用2sum的思想，先两层循环，然后最后两位用夹逼，注意判断重复
class Solution { public: vector<vector<int> > fourSum(vector<int> &num, int target) { int n=num.size(); sort(num.begin(),num.end()); vector<vector<int>> res; for(int i=0;i<n;++i) { if(i>0&&num[i]==num[i-1]) continue; int t1 = target-num[i]; for(int j=i+1;j<n;++j) { if(j>i+1&&num[j]==num[j-1]) continue; int t2 = t1-num[j]; int l=j+1,r=n-1; while(l<r) { int t3 =t2-num[l]-num[r]; if(t3==0) { res.push_back({num[i],num[j],num[l],num[r]}); while(l<r&&num[l]==num[l+1]) l++; while(l<r&&num[r]==num[r-1]) r--; l++;r--; } else if(t3 >0) l++; else r--; } } } return res; } };
原文：https://www.cnblogs.com/zl1991/p/12783091.html