lc18. 四数之和

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

题解

双指针，题目中会超过 int

参考代码

class Solution {
public:
    vector<vector<int>> fourSum(vector<int>& a, int s) {
        vector<vector<int>>ans;
        sort(a.begin(), a.end());
        int n = a.size();
        for(int i=0; i<n; ++i) {
            if(i&&a[i-1]==a[i]) continue;
            map<int,int>mp;
            for(int j=i+1;j<n;j++) {
                if(mp[a[j]]==1) continue;
                mp[a[j]] = 1;
                long long s1 = (long long)s - a[i] - a[j];
                int k=j+1;
                int t=n-1;
                while(k<t) {
                    long long s2 = a[k] + a[t];
                    if(s2==s1) {
                        vector<int>tmp{a[i], a[j], a[k], a[t]};
                        ans.push_back(tmp);
                        int now = a[k];
                        k++;
                        while(k<=t&&a[k]==now) k++; 
                        // cout<<k<<" "<<t<<endl;
                    }
                    else if(s2<s1) {
                        k++;
                    }
                    else {
                        t--;
                    }
                }
            }
        }
        return ans;
    }
};