Simple C++ solution with hash and time is O(n^3)


  • 1
    B
    vector<vector<int>> fourSum(vector<int>& nums, int target) {
    int n=nums.size();
    sort(nums.begin(), nums.end());
    int a,b,c,d;
    int now;
    vector<vector<int>>result;
    map<vector<int>, bool>hash;
    for (a=0; a<n; a++) {
        for (b=a+1; b<n; b++) {
            c=b+1;d=n-1;
            while(c<d) {
                now=nums[a]+nums[b]+nums[c]+nums[d];
                if (now<target) {
                    c++;
                }
                if (now>target) {
                    d--;
                }
                if (now==target) {
                    vector<int>temp;
                    while (c<d&&nums[c]==nums[c+1]) c++;
                    while (c<d&&nums[d]==nums[d-1]) d--;
                    temp.push_back(nums[a]);
                    temp.push_back(nums[b]);
                    temp.push_back(nums[c]);
                    temp.push_back(nums[d]);
                    if (hash.count(temp)) {
                        c++;
                        continue;
                    }
                    result.push_back(temp);
                    hash[temp]=true;
                    c++;
                }
            }
        }
    }
    return result;
    

    }


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.