18. 4Sum

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

Note:

The solution set must not contain duplicate quadruplets.

使用三重for循环，在最后一层使用哈希表，复杂度为O(n^3)，为了避免重复的解，使用set存储得到的vector

class Solution {
public:
    vector<vector<int> > fourSum(vector<int>& nums, int target) {
        int len = nums.size();
        set<vector<int>> data;
        unordered_map<int, int> data_map;
        sort(nums.begin(), nums.end());
        for(int i=0;i<len;i++){
            data_map[nums[i]] = i;
        }
        for(int i = 0; i < len-3; i++){
            for(int j=i+1; j<len-2; j++){
                for(int k=j+1; k<len-1; k++)
                {
                    int findNum = target - nums[i] - nums[j] - nums[k];
                    if(data_map.find(findNum) != data_map.end() && data_map[findNum] > k){
                        vector<int> temp = {nums[i], nums[j], nums[k], findNum};
                        data.insert(temp);
                    }
                }
            }
        }
        return vector<vector<int>>(data.begin(), data.end());
    }
};