LeetCode 18. 4Sum

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.

Note: The solution set must not contain duplicate quadruplets.

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

解析：
给定一组数值和目标值，从数组中求的4个数值，使其和为给定目标值。
要求结果由小到大排列，不含重复结果。
题目跟3Sum类似，只不过要求4个数字的和，复杂度更进一步，时间复杂度为\(O(n^3)\)。
具体代码如下：

[cc lang=”C++”]
class Solution {
public:
vector> fourSum(vector& nums, int target) {
vector< vector > result;
if (nums.size() < 4) return result; sort(nums.begin(), nums.end());//首先排序 unordered_map > > cache;//建立两个数之和的对应关系
for(size_t a=0; a < nums.size(); ++a) { for(size_t b=a+1; b < nums.size(); ++b) { cache[nums[a] + nums[b]].push_back(pair(a,b));
}
}
for(size_t c=0; c