首页 > 代码库 > [LeetCode] 4Sum
[LeetCode] 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:
- Elements in a quadruplet (a,b,c,d) must be in non-descending order. (ie, a ≤ b ≤ c ≤ d)
- 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)
分析：
方法一：
类似3Sum，先排序，这后两重循环，然后对最后的一个数组设两个指针遍历。这里注意重复的问题，复杂度 排序O(log n)+遍历O(n^3)
code如下
1 class Solution { 2 private: 3 vector<vector<int> > ret; 4 public: 5 vector<vector<int> > fourSum(vector<int> &num, int target) { 6 // Start typing your C/C++ solution below 7 // DO NOT write int main() function 8 sort(num.begin(), num.end()); 9 10 ret.clear();11 12 for(int i = 0; i < num.size(); i++)13 {14 //skip dupliated15 if (i > 0 && num[i] == num[i-1])16 continue;17 18 for(int j = i + 1; j < num.size(); j++)19 {20 //skip dupliated21 if (j > i + 1 && num[j] == num[j-1])22 continue;23 24 int k = j + 1;25 int m = num.size() - 1;26 27 while(k < m)28 {29 if (k > j + 1 && num[k] == num[k-1])30 {31 //skip dupliated32 k++;33 continue;34 }35 36 if (m < num.size() - 1 && num[m] == num[m+1])37 {38 //skip dupliated39 m--;40 continue;41 }42 43 int sum = num[i] + num[j] + num[k] + num[m];44 45 if (sum == target)46 {47 vector<int> tmp;48 tmp.push_back(num[i]);49 tmp.push_back(num[j]);50 tmp.push_back(num[k]);51 tmp.push_back(num[m]);52 ret.push_back(tmp);53 k++;54 }55 else if (sum < target)56 k++;57 else58 m--; 59 }60 }61 }62 63 return ret;64 }65 };
方法二：那么时间复杂度能不能更好呢？其实我们可以考虑用二分法的思路，如果把所有的两两pair都求出来，然后再进行一次Two Sum的匹配，我们知道Two Sum是一个排序加上一个线性的操作，并且把所有pair的数量是O((n-1)+(n-2)+...+1)=O(n(n-1)/2)=O(n^2)。所以对O(n^2)的排序如果不用特殊线性排序算法是O(n^2*log(n^2))=O(n^2*2logn)=O(n^2*logn)，算法复杂度比上一个方法的O(n^3)是有提高的。
思路虽然明确，不过细节上会多很多情况要处理。首先，我们要对每一个pair建一个数据结构来存储元素的值和对应的index，这样做是为了后面当找到合适的两对pair相加能得到target值时看看他们是否有重叠的index，如果有说明它们不是合法的一个结果，因为不是四个不同的元素。接下来我们还得对这些pair进行排序，所以要给pair定义comparable的函数。最后，当进行Two Sum的匹配时因为pair不再是一个值，所以不能像Two Sum中那样直接跳过相同的，每一组都得进行查看，这样就会出现重复的情况，所以我们还得给每一个四个元素组成的tuple定义hashcode和相等函数，以便可以把当前求得的结果放在一个HashSet里面，这样得到新结果如果是重复的就不加入结果集了。
如果使用的是基于红黑树的map，查找效率O（logn），基于hash的map，查找复杂度是O（n），unordered_multimap是基于C++11的hash map
第二种方法比第一种方法时间上还是有提高的，其实这道题可以推广到k-Sum的问题，基本思想就是和第二种方法一样进行二分，然后两两结合，不过细节就非常复杂了（这点从上面的第二种解法就能看出来），所以不是很适合在面试中出现，有兴趣的朋友可以进一步思考或者搜索网上材料哈
code如下
1 class Solution { 2 public: 3 vector<vector<int>> fourSum(vector<int>& num, int target) { 4 vector<vector<int>> result; 5 if (num.size() < 4) return result; 6 sort(num.begin(), num.end()); 7 unordered_multimap<int, pair<int, int>> cache;// 基于哈希，可以存储多个相同的key 值 8 for (int i = 0; i + 1 < num.size(); ++i) //保存所有的两两配对 9 for (int j = i + 1; j < num.size(); ++j)10 cache.insert(make_pair(num[i] + num[j], make_pair(i, j)));11 for (unordered_multimap<int, pair<int, int>>::iterator i = cache.begin(); i != cache.end(); ++i) {12 int x = target - i->first;//计算另外的数13 pair<unordered_multimap<int, pair<int, int>>::iterator,unordered_multimap<int, pair<int, int>>::iterator> range;14 //auto range15 range = cache.equal_range(x);//在cache中查找16 //返回的i，j就是指向满足条件的首位迭代器17 for (unordered_multimap<int, pair<int, int>>::iterator j = range.first; j != range.second; ++j) {18 int idx1 = i->second.first;19 int idx2 = i->second.second;20 int idx3 = j->second.first;21 int idx4 = j->second.second;22 if (idx1 != idx3 && idx1 != idx4 && idx2 != idx3 && idx2 != idx4) {23 vector<int> vec = { num[idx1], num[idx2], num[idx3], num[idx4] };24 sort(vec.begin(), vec.end());25 result.push_back(vec);26 }27 }28 }29 sort(result.begin(), result.end());30 result.erase(unique(result.begin(), result.end()), result.end());31 /*32 * unique(result.begin(), result.end()) 将result unique化，返会的是不重复的最后一个元素下一个的迭代器，33 * erase将后续重复的内容擦除34 */35 return result;36 }37 };