4Sum

最后更新于:2022-04-01 22:55:03

## 一、题目描述 ![](https://docs.gechiui.com/gc-content/uploads/sites/kancloud/2016-01-05_568bb5e83b2cf.jpg) ## 二、解题技巧 这道题从表面上看与3Sum极其相似,事实上确实可以使用相同的思维和方法,只不过这样做的话,时间复杂度为O(n^3),空间复杂度为O(1)将超时。 这道题也可以在排序之后先计算后面两个数的和,将其方法一个哈希表中,由于可能存在不同的两个数的和为相同值,因此,可以考虑将和为相同的值放在一个链表中,然后将变量头放在哈希表中。然后再按照3Sum的思路,不过第三个数在这里变成了第三个和第四个数的和,通过哈希表可以方便地找到和为固定值的数的链表,就可以找到符合条件的四个数。这种方法的时间复杂度为O(n^2),空间复杂度也为O(n^2)。 ## 三、实例代码 ~~~ // 该算法使用3Sum的思路来实现 #include #include #include using namespace std; class solution { public: vector > fourSum(vector &num, int target) { vector > result; int Size = num.size(); if (Size < 4) return result; // 对输入的数据进行排序 sort(num.begin(), num.end()); for (int first = 0; first < (Size - 3); first++) { if ((first != 0) && (num[first] == num[first - 1])) { continue; } int first_num = num[first]; for (int second = first + 1; second < (Size - 2); second++) { if ((second != first + 1) && (num[second] == num[second - 1])) { continue; } int second_num = num[second]; int third = second + 1; int forth = Size - 1; // 对第三和第四个数进行左右夹逼 while (third < forth) { int third_num = num[third]; int forth_num = num[forth]; int Sum = first_num + second_num + third_num + forth_num; if (Sum == target) { // 存放一维数据 vector temp; temp.push_back(first_num); temp.push_back(second_num); temp.push_back(third_num); temp.push_back(forth_num); // 将组合存入容器result中 result.push_back(temp); third++; while ((third < Size - 1) && (num[third] == num[third - 1])) { third++; } forth--; while ((forth > second) && (num[forth] == num[forth + 1])) { forth--; } } if (Sum > target) { forth--; while ((forth > second) && (num[forth] == num[forth + 1])) { forth--; } } if (Sum < target) { third++; while ((third < Size) && (num[third] == num[third - 1])) { third++; } } } } } return result; } }; ~~~ 测试: ~~~ #include "solution.h" using namespace std; int main() { solution a; int size = 200; // 数据的个数 vector num(size); // 用于存放数据的容器 vector > result; // 存放算法的运行结果 for (int i = 0; i < size; i++) num.push_back(rand() % 30 - 20); // 随机生成数据 int target = 0; result = a.fourSum(num, target); for (vector >::size_type j = 0; j < result.size(); j++) { for (vector::size_type k = 0; k < result[j].size(); k++) { cout << result[j][k] << " "; } cout << endl; } getchar(); return 0; } ~~~ 一个输出结果: ![](https://docs.gechiui.com/gc-content/uploads/sites/kancloud/2016-01-05_568bb5e864da4.jpg) ## 四、体会 这道题是3Sum的一种延伸,但需要转化一种思路以降低计算复杂度。如果仅仅按照3Sum的延伸来做这道题的话,算法的空间复杂度会达到O(n^3),但是空间复杂度为O(1)。可以换一种思路,在排序之后,先计算后面两个数的和,并用哈希表存储起来,然后就将问题转变为了3Ssum的问题,只不过计算出第三个数之后,还需要在哈希表中找到和满足条件的第三个数和第四个数。
';