[leetcode] 4sum


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.

Note:

  • Elements in a quadruplet (a,b,c,d) must be in non-descending order. (ie, abcd)
  • The solution set must not contain duplicate quadruplets.
    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)

所有的Ksum问题都可以通过枚举一个元素,退化成K-1sum,k-2sum…最终变成2sum,然后用2sum的双指针算法(头指针,尾指针)在线性时间解决,也就是Ksum问题有一个o(n^(k-1))的通解。

版本一:o(n^3)

class Solution {
public:
    vector<vector<int> > fourSum(vector<int> &num, int target) {
        vector<vector<int>> re;
        if(num.size() < 4){
            return re;
        }
        sort(num.begin(), num.end());
        for(int i = 0; i < num.size() - 3; ){
            for(int j = i + 1; j < num.size() - 2; ){
                int a = num[i];
                int b = num[j];
                int thisTarget = target - a - b;
                int k = j + 1;
                int l = num.size() - 1;
                while(k < l){
                    int sum = num[k] + num[l];
                    if(sum == thisTarget){
                        vector<int> thisRe;
                        thisRe.push_back(a);
                        thisRe.push_back(b);
                        thisRe.push_back(num[k]);
                        thisRe.push_back(num[l]);
                        re.push_back(thisRe);
                        k++;
                        while(k < l && num[k] == num[k - 1]){
                            k++;
                        }
                        l--;
                        while(l > k && num[l] == num[l + 1]){
                            l--;
                        }
                        
                    }
                    else if(sum > thisTarget){
                        l--;
                        while(l > k && num[l] == num[l + 1]){
                            l--;
                        }
                    }
                    else{
                        k++;
                        while(k < l && num[k] == num[k - 1]){
                            k++;
                        }
                    }
                }
                j++;
                while(j < num.size() && num[j] == num[j - 1]){
                    j++;
                }
            }
            i++;
            while(i < num.size() && num[i] == num[i - 1]){
                i++;
            }
        }
        return re;
    }
    
};

AC.

Untitled

 

尝试用空间换时间,加入hashtable,key为每个2-pair的sum,value为一个vector,储存所有和为sum的id-pair。复杂度o(n^2*k),k为建哈希表和查哈希表的复杂度,与数据和哈希表的结构有关。但是却超时。

版本二:o(n^2*k) 超时,好奇怪,求高人指点。

class Solution {
public:
    unordered_map<int, vector<vector<int>>> hashTable; 
    vector<vector<int>> re;
    vector<vector<int>> fourSum(vector<int> &num, int target) {
        if(num.size() < 4){
            return re;
        }
        sort(num.begin(), num.end());
        //build hashmap
        for(unsigned int i = 0; i < num.size(); ){
            for(unsigned int j = i + 1; j < num.size(); ){
                int sum = num[i] + num[j];
                vector<int> thisPair;
                thisPair.push_back(i);
                thisPair.push_back(j);
                if(hashTable.find(sum) == hashTable.end()){//not found
                    vector<vector<int>> pairs;
                    pairs.push_back(thisPair);
                    hashTable[sum] = pairs;
                }
                else{//found
                    hashTable[sum].push_back(thisPair);
                }
                j++;
                while(j < num.size() && num[j] == num[j - 1]){
                    j++;
                }
            }
            i++;
            while(i < num.size() && num[i] == num[i - 1]){
                    i++;
            }
        }
        //search hashmap
        for(unsigned int i = 0; i < num.size(); ){
            for(unsigned int j = i + 1; j < num.size(); ){
                int a = num[i];
                int b = num[j];
                int thisTarget = target - a - b;
                if(hashTable.find(thisTarget) != hashTable.end()){//found
                    vector<vector<int>> pairs = hashTable[thisTarget];
                    for(unsigned int k = 0; k < pairs.size(); k++){
                        int idx = pairs[k][0];
                        int idy = pairs[k][1];
                        if(idx > j){//not duplicated
                            vector<int> thisRe;
                            thisRe.push_back(a);
                            thisRe.push_back(b);
                            thisRe.push_back(num[idx]);
                            thisRe.push_back(num[idy]);
                            re.push_back(thisRe);   
                        }
                    }
                }
                j++;
                while(j < num.size() && num[j] == num[j - 1]){
                    j++;
                }
            }
            i++;
            while(i < num.size() && num[i] == num[i - 1]){
                i++;
            }
        }
        return re;
    }
};

 

 

 

 

 

Leave a comment

Your email address will not be published.

This site uses Akismet to reduce spam. Learn how your comment data is processed.