1 class Solution { 2 public: 3     vector<vector<int>> fourSum(vector<int>& nums, int target) { 4         vector<vector<int>> result; 5         if (nums.size() < 4) return result; 6         map<int, vector<pair<int, int>>> cache; 7         set<vector<int>> res; 8         sort(nums.begin(), nums.end()); 9         for (int i = 0; i < nums.size() - 1; ++i) {10             for (int j = i + 1; j < nums.size(); ++j) {11                 cache[nums[i] + nums[j]].push_back(pair<int, int>(i, j));12             }13         }14         for (int i = 0; i < nums.size() - 3; ++i) {15             for (int j = i + 1; j < nums.size() - 2; ++j) {16                 int gap = target - nums[i] - nums[j];17                 if (cache.find(gap) != cache.end()) {18                     vector<int> temp;19                     for (auto item : cache[gap]) {20                         temp.clear();21                         if (i != item.first && i != item.second && j != item.first && j != item.second) {22                             temp = vector<int>{ nums[i], nums[j], nums[item.first], nums[item.second] };23                             sort(temp.begin(), temp.end());24                             res.insert(temp);25                         }26                     }27                 }28             }29         }30         result = vector<vector<int>>(res.begin(), res.end());31         return result;32     }33 };

 1 class Solution { 2 public: 3     vector<vector<int>> fourSum(vector<int>& nums, int target) { 4         vector<vector<int>> result; 5         if (nums.size() < 4) return result; 6         else { 7             multimap<int, pair<int, int>> cache; 8             for (int i = 0; i < nums.size() - 1; ++i) { 9                 for (int j = i + 1; j < nums.size(); ++j) {10                     cache.insert(pair<int, pair<int, int>>(nums[i] + nums[j], pair<int, int>(i, j)));11                 }12             }13             for (const auto& item : cache) {14                 int gap = target - item.first;15                 auto range = cache.equal_range(gap);16                 for (auto i = range.first; i != range.second; ++i) {17                     int a = item.second.first;18                     int b = item.second.second;19                     int c = i->second.first;20                     int d = i->second.second;21                     if (a != c && a != d && b != c && b != d) {22                         vector<int> vec{ nums[a], nums[b], nums[c], nums[d] };23                         sort(vec.begin(), vec.end());24                         result.push_back(vec);25                     }26                 }27             }28             sort(result.begin(), result.end());29             result.erase(unique(result.begin(), result.end()), result.end());30             return result;31         }32     }33 };