4 Sum

Given an array S of n integers, are there elements a, b, c, and d in S such that a + b + c + d = target? Find all unique quadruplets in the array which gives the sum of target.

Discussion

先排序，再夹逼，O(n^3) runtime.

Solution

class Solution {
public:
    /**
     * @param numbers: Give an array numbersbers of n integer
     * @param target: you need to find four elements that's sum of target
     * @return: Find all unique quadruplets in the array which gives the sum of 
     *          zero.
     */
    vector<vector<int> > fourSum(vector<int> nums, int target) {
        // write your code here
        vector<vector<int> > result;
        if(nums.size() < 4) return result;
        int n = nums.size();
        sort(nums.begin(), nums.end());
        for(int i=0; i<n-3; i++) {
            for(int j=i+1; j<n-2; j++) {
                int newTarget = target - nums[i] - nums[j];
                int start = j+1; 
                int end = n-1;
                while(start < end) {
                    if(nums[start] + nums[end] == newTarget) {
                        result.push_back({nums[i], nums[j], nums[start], nums[end]});
                        start++;
                        end--;
                    } else if(nums[start] + nums[end] > newTarget) {
                        end--;
                    } else {
                        start++;
                    }
                }
            }
        }
        sort(result.begin(), result.end());
        result.erase(unique(result.begin(), result.end()), result.end());
        return result;
    }
};

也可以先用一个hash存下两个数的和，再找剩下两个。

class Solution {
public:
    /**
     * @param numbers: Give an array numbersbers of n integer
     * @param target: you need to find four elements that's sum of target
     * @return: Find all unique quadruplets in the array which gives the sum of 
     *          zero.
     */
    vector<vector<int> > fourSum(vector<int> nums, int target) {
        // write your code here
        vector<vector<int> > result;
        if(nums.size() < 4) return result;
        int n = nums.size();
        sort(nums.begin(), nums.end());
        unordered_map<int, vector<pair<int, int> > > map;
        for(int i=0; i<n; i++) {
            for(int j=i+1; j<n; j++) {
                int sum = nums[i] + nums[j];
                pair<int,int> p (i,j);
                map[sum].push_back(p);
            }
        }
        for(int i=0; i<n; i++) {
            for(int j=i+1; j<n; j++) {
                int key = target - nums[i] - nums[j];
                if(map.find(key) == map.end()) 
                    continue;
                vector<pair<int, int> > vec = map[key];
                for(int m=0; m<vec.size(); m++) {
                    pair<int,int> p = vec[m];
                    if(i<=p.second) 
                        continue;
                    result.push_back({nums[p.first], nums[p.second], nums[i], nums[j]});
                }
            }
        }
        sort(result.begin(), result.end());
        result.erase(unique(result.begin(), result.end()), result.end());
        return result;
    }
};