一、题目

 二、算法

  使用双指针

class Solution {
public:
    vectorint>> fourSum(vector<int>& nums, int target) {
        vectorint>> result;
        sort(nums.begin(), nums.end());
        for(int i=0; i){
            if(i>0 && nums[i]==nums[i-1]){
                continue;
            }
            for(int j=i+1; j){
                if(j>i+1 && nums[j]==nums[j-1]){
                    continue;
                }
                int left = j+1;
                int right = nums.size()-1;
                while(left < right){
                    if(nums[i] + nums[j] > target - (nums[left]+nums[right])){
                        right--;
                    }
                    else if (nums[i] + nums[j] < target - (nums[left] + nums[right] )){
                        left++;
                    }
                    else{
                        result.push_back(vector<int>{nums[i], nums[j], nums[left], nums[right]});
                        left++;
                        right--;
                    }
                    while(left> j+1 && left < right && nums[left]==nums[left-1]){
                            left++;
                        }
                        while(right < nums.size()-1 && left < right && nums[right]==nums[right+1]){
                            right--;
                        }
                }
            }
        }
        return result;
    }
};

三、尝试用unordered_map

class Solution {
public:
    vectorint>> fourSum(vector<int>& nums, int target) {
        vectorint>> result;
        
        unordered_map<int, array<int, 4>> record;
        for(int i=0; i){
            for(int j=i+1; j){  
                if(record.find(nums[i]+nums[j])!=record.end()){
                    record[nums[i]+nums[j]][0] = nums[i];
                    record[nums[i]+nums[j]][1] = nums[j];
                }
            }
        }
        for(int i=0; i){
            for(int j=i+1; j){  
                auto final = record.find(target-nums[i]-nums[j]);
                if(final != record.end()){
                    result.push_back(vector<int>{nums[i], nums[j], final->second[0], final->second[1]});
                }
            }
        }
        return result;
    }
};

    本来尝试用这种方法，可以把效率提高到O(n^2)，但是好像并没有跑通，始终都返回空。