O(n^3)

for (int a = ...) {

for (int b = a + 1...) {

two sum c+d

}

}

hash map

4 -> a + b

   c + d

for (a ...)

for\(b...\) 

     hashmap.add\(a + b\);

for (c...)

for (d...) {

hashmap[target - c - d]

    vector<vector<int> > fourSum(vector<int> nums, int target) {
        // write your code here
        vector<vector<int> > results;
        int size = nums.size();
        if (size < 4) {
            return results;
        }
        unordered_map<int, vector<pair<int, int>>> map;
        sort(nums.begin(), nums.end());
        for (int i = 0; i < size; i++) {
            if (i != 0 && nums[i - 1] == nums[i]) {
                continue;
            }
            for (int j = i + 1; j < size; j++) {
                if (j != i + 1 && nums[j - 1] == nums[j]) {
                    continue;
                }
                int sum = nums[i] + nums[j];
                if (map.find(sum) == map.end()) {
                    map.insert({sum, vector<pair<int, int>>()});
                }
                map[sum].push_back(make_pair(i, j));
            }
        }

        for (int m = 0; m < size; m++) {
            if (m != 0 && nums[m - 1] == nums[m]) {
                continue;
            }
            for (int n = m + 1; n < size; n++) {
                if (n != m + 1 && nums[n - 1] == nums[n]) {
                    continue;
                }
                int sum = nums[m] + nums[n];
                if (map.find(target - sum) != map.end()) {
                    for (pair<int, int> p : map[sum]) {
                        vector<int> solution;
                        solution.push_back(nums[m]);
                        solution.push_back(nums[n]);
                        solution.push_back(nums[p.first]);
                        solution.push_back(nums[p.second]);
                        results.push_back(solution);
                    }
                }
            }
        }

        return results;
    }
};