3 Sum
LeetCode笔记 阅读(407)
编号 : 15 难度 : <font color="orange">Medium</font> # 题目 : >Given an array `nums` of n integers, are there elements `a`, `b`, `c` in `nums` such that `a + b + c = 0`? Find all unique triplets in the array which gives the `sum` of zero. > >**Note**: > >The solution set must not contain duplicate triplets. > >**Example**: > >>``` >>Given array nums = [-1, 0, 1, 2, -1, -4], >> >>A solution set is: >>[ >> [-1, 0, 1], >> [-1, -1, 2] >>] >>``` # 解 : ```Cpp class Solution { public: vector<vector<int>> threeSum(vector<int>& nums) { vector<vector<int>> ret; /* 为了优化搜索过程,对数据进行排序,同时可以避免重复 */ sort(nums.begin(), nums.end()); for(int a = 0; a < nums.size();) { // 由于已经排序了a < b < c, // 所以如果0 < a,则必然有a+b+c > 0 if(nums[a] > 0) { break; } // b和c从两头往中间找 int b = a + 1; int c = nums.size() - 1; while(b < c) { int sum = nums[b] + nums[c]; if(sum < -nums[a]) { b++; } else if(sum > -nums[a]) { c--; } else { // 插入一组结果 ret.push_back({nums[a], nums[b], nums[c]}); // 跳过重复 for(;b < c && nums[b] == nums[b+1]; b++); for(;b < c && nums[c] == nums[c-1]; c--); // 需要再移动一次 b++; c--; } } // 跳过重复数据 for(;a < nums.size() - 1 && nums[a] == nums[a+1]; a++); // 需要再移动一次 a++; } return ret; } }; ``` # 分析 : 三层循环嵌套遍历a、b、c,得出全部结果的复杂度为O(n^3)。除此外,判断是否重复也需要消耗大量的时间。因此必须进行优化。 上面的解法首先把问题从`a + b + c = 0`转换为`b + c = -a`的问题。 将数组排序,并将`b`和`c`分别放在剩余搜索范围的两端,设`sum = b + c`, 则需要增大`sum`时只能将`b`向后移动,反之则只能将`c`向前移动, 这样一来对`b`和`c`的搜索复杂度从`O(n^2)`优化为了`O(n)`, 整个算法的复杂度变成了`O(n^2)`,同时由于排了序,可以轻松的跳过重复解。 另外,根据LeetCode题目上的三条hide hint,使用哈希表也能写出一些解法,例如下面的代码,但是下面的代码依然`Time Limit Exceeded`了。 ```Cpp class Solution { public: vector<vector<int>> threeSum(vector<int>& nums) { vector<vector<int>> ret; /* 为了避免重复,对数据进行排序 */ sort(nums.begin(), nums.end()); /* 用来查找 */ unordered_set<int> values_set; for(size_t a = 0; a < nums.size();) { values_set.clear(); for(size_t c = a + 1; c < nums.size();) { /* 减去第一个值和最后一个值,来搜索中间的那个值 * 这样向map中插入值的操作可以放在每次查找之后 * 我刻意在变量名上使用a和c而跳过b,使其更加直观 */ int value_b = 0 - nums[a] - nums[c]; auto n = values_set.find(value_b); if(value_b < nums[a+1]) { // n比第一个可取值小,不可能有解,直接跳过 break; } else if(value_b > nums[c-1] || n == values_set.end()) { // 保存map并继续循环 values_set.insert(nums[c]); c++; continue; } // 保存结果 ret.push_back({nums[a], nums[c], value_b}); // 跳过重复数据 int value_c = nums[c]; for(; c < nums.size() && value_c == nums[c]; c++); } // 跳过重复数据 int value_a = nums[a]; for(; a < nums.size() && value_a == nums[a]; a++); } return ret; } }; ``` * 根据该题下的3个隐藏提示,使用哈希表缓存数据,然而还是`Time Limit Exceeded`了。