Leetcode-18:4Sum

2017-07-12

问题描述：

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.

问题示例

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]
]

我的答案

//超时，其实时间复杂度为o(n^2)
class Solution {
public:
    vector<vector<int>> fourSum(vector<int>& nums, int target) {
    vector<vector<int>> output;
    vector<vector<int>> addsum;
    vector<int>temp;
    for(int i=0;i<nums.size();i++){
        for (int j=i+1;j<nums.size();j++) {
            temp.clear();
            temp.push_back(i);
            temp.push_back(j);
            addsum.push_back(temp);
        }
    }
    //排序
    int min;
    for(int i=0;i<addsum.size();i++){
        min = i;
        for(int j=i+1;j<addsum.size();j++){
            if(nums[addsum[j][0]]+nums[addsum[j][1]]<nums[addsum[min][0]]+nums[addsum[min][1]]){
                min = j;
            }
        }
        addsum[i].swap(addsum[min]);
    }
    int left=0;
    int right=addsum.size()-1;
    int sameleft=0;
    map<string,int>tempmap;
    string key="";
    while(left<right){
        key="";
        if(nums[addsum[left][0]]+nums[addsum[left][1]]+nums[addsum[right][0]]+nums[addsum[right][1]]==target){
            if(addsum[left][0]!=addsum[right][0]&&addsum[left][0]!=addsum[right][1]&&addsum[left][1]!=addsum[right][0]&&addsum[left][1]!=addsum[right][1]){
                temp.clear();
                temp.push_back(nums[addsum[left][0]]);
                temp.push_back(nums[addsum[left][1]]);
                temp.push_back(nums[addsum[right][0]]);
                temp.push_back(nums[addsum[right][1]]);
                sort(temp.begin(),temp.end());
                for(int k=0;k<4;k++){
                    key = key+to_string(temp[k]).c_str();
                }
                if(tempmap.count(key)==0){  //该序列不存在
                    output.push_back(temp);
                    tempmap.insert(pair<string,int>(key,1));
                }
            }
            if(nums[addsum[left][0]]+nums[addsum[left][1]]==nums[addsum[left+1][0]]+nums[addsum[left+1][1]]){
                if(nums[addsum[left][0]]+nums[addsum[left][1]]!=nums[addsum[sameleft][0]]+nums[addsum[sameleft][1]]){
                    sameleft = left;
                }
                left++;
            }else if(nums[addsum[left][0]]+nums[addsum[left][1]]!=nums[addsum[left+1][0]]+nums[addsum[left+1][1]]&&nums[addsum[right][0]]+nums[addsum[right][1]]==nums[addsum[right-1][0]]+nums[addsum[right-1][1]]){
                right--;
                left=sameleft;
            }else{
                if(nums[addsum[left][0]]+nums[addsum[left][1]]==nums[addsum[sameleft][0]]+nums[addsum[sameleft][1]]){
                    right--;
                    left=sameleft;
                }else{
                    left++;
                    right--;
                }
            }
        }else if(nums[addsum[left][0]]+nums[addsum[left][1]]+nums[addsum[right][0]]+nums[addsum[right][1]]>target){
            right--;
        }else{
            left++;
        }
    }
    return output;
}
};
//AC,时间复杂度o(n^3)
vector<vector<int>> fourSum(vector<int>& nums, int target) {
    set<vector<int> > set;
    vector<int> temp;
    sort(nums.begin(), nums.end());
    int left=0;
    int right=0;
    for(int i=0;i<int(nums.size()-3);i++){
        for(int j=i+1;j<int(nums.size()-2);j++){
            left=j+1;
            right=int(nums.size()-1);
            while(left<right){
                if(nums[i]+nums[j]+nums[left]+nums[right]==target){
                    temp.clear();
                    temp.push_back(nums[i]);
                    temp.push_back(nums[j]);
                    temp.push_back(nums[left]);
                    temp.push_back(nums[right]);
                    set.insert(temp);
                    left++;
                    right--;
                }else if(nums[i]+nums[j]+nums[left]+nums[right]>target){
                    right--;
                }else{
                    left++;
                }
            }
        }
    }
    return vector<vector<int> > (set.begin(), set.end());
}

其他高效答案

class Solution {
public:
    vector<vector<int>> fourSum(vector<int>& nums, int target) {
        vector<vector<int>> total;
        int n = nums.size();
        if(n<4)  return total;
        sort(nums.begin(),nums.end());
        for(int i=0;i<n-3;i++)
        {
            if(i>0&&nums[i]==nums[i-1]) continue;
            if(nums[i]+nums[i+1]+nums[i+2]+nums[i+3]>target) break;
            if(nums[i]+nums[n-3]+nums[n-2]+nums[n-1]<target) continue;
            for(int j=i+1;j<n-2;j++)
            {
                if(j>i+1&&nums[j]==nums[j-1]) continue;
                //j = std::distance(nums.begin(),std::upper_bound(nums.begin()+j, nums.end()-2,nums[j]));
                if(nums[i]+nums[j]+nums[j+1]+nums[j+2]>target) break;
                if(nums[i]+nums[j]+nums[n-2]+nums[n-1]<target) continue;
                int left=j+1,right=n-1;
                while(left<right){
                    int sum=nums[left]+nums[right]+nums[i]+nums[j];
                    if(sum<target) left++;
                    else if(sum>target) right--;
                    else{
                        total.push_back(vector<int>{nums[i],nums[j],nums[left],nums[right]});
                        left = std::distance(nums.begin(),std::upper_bound(nums.begin()+i, nums.end()-2,nums[left]));
                        right = std::distance(nums.begin(),std::lower_bound(nums.begin()+i, nums.end()-2,nums[right]));
                        if(left >right) break;
                    }
                }
            }
        }
        return total;
    }
};