当前位置 博文首页 > 3Sum_让代码改变世界：LeetCode 15
好几天没有写了，主要是因为这几天事情比较多，而且这道题也是有点儿小复杂，从上面统计的通过率可以看出，虽然本题的难度为中等，但通过率算是最低的题目之一了，到底是个什么题呢，我们来看一下
Given an array?S?of?n?integers, are there elements?a,?b,?c?in?S?such that?a?+?b?+?c?= 0? Find all unique triplets in the array which gives the sum of zero.
Note:
For example, given array S = {-1 0 1 2 -1 -4},
A solution set is:
(-1, 0, 1)
(-1, -1, 2)
题目的要求很容易理解，给你一个数组，找出里面所有和为零的组合，要求输出结果按顺序排列且没有重复的组合。
最简单的方法可以采用蛮力法，显然这是一个O(n^3)的算法，这当然不是我们想要的，而且实际操作中还要排序，去重复，如果里面重复的组合比较多，那去重复的时间恐怕比找组合的时间还要多。
怎么分析呢，说实在的我在这方面走了很多弯路，但说是弯路，基本方向又是对的，为了完整性还是说一下吧。首先分析问题，三个数相加等于0，那肯定有正有负，还有可能有零，，，，经过简单的分析我作出了这样的算法：
1）将数组排序，然后将负数、零、正数分别存放到不同的容器中。
2）判断零元素的个数，如果存在那么就在正数里查找有没有对应的负数，因为已经排序，所以可以采用二分查找。如果大于等于3那么全0是一组。
3）历遍所有负数，然后在正数里采用第一题中的算法“两头搜索”看是否有匹配的两个正数；然后换历遍所有负数，看是否有匹配的负数。
4）去重复。
明白人可能已经看出来了，没错，我的算法太复杂了，东拼西凑的。不过由于我强大的对胜利的渴望，我还是把算法用程序实现了，结果也正确了，怎么说呢算是成功了吧，但并没有通过leetcode的验证，因为时间超了。后来几经改进，最终还是没有成功，哎，又是一次失败
后来就看了大神的代码，发现我完全是将问题复杂化了，看了大神的代码后，我又自己分析了一下，写出了下面的代码，这个说是抄来的也是，其实是找到了改进点，代码还是完全自己写的
class Solution {
public:
vector<vector<int>> threeSum(vector<int>& nums) {
//获取数组长度
int len=nums.size();
//定义返回结果
vector<vector<int>> result;
//判断边界输入
if(len<3) return result;
//将数组排序
sort(nums.begin(),nums.end());
int lef=0,rig=0;
vector<int> temp;temp.resize(3);
for(int i=0;i<len-2;++i)
{
lef=i+1;rig=len-1;
if(i!=0 && nums[i]==nums[i-1])continue;
while(lef<rig)
{
if(lef!=i+1&&nums[lef]==nums[lef-1])
{
lef++;
continue;
}
if(rig!=len-1&&nums[rig]==nums[rig+1])
{
rig--;
continue;
}
if(nums[i]+nums[lef]+nums[rig]==0)
{
temp[0]=nums[i];
temp[1]=nums[lef];
temp[2]=nums[rig];
result.push_back(temp);
lef++;rig--;
}
else if(nums[i]+nums[lef]+nums[rig]<0)
{
lef++;
}
else
{
rig--;
}
}
}
return result;
}
};具体来说，本题就是先将数组排序，然后用i作为下标历遍整个数组，历遍过程中将后面的部分作为第一题中的查找部分，看是否存在三个数为零的情况。但与第一题不同的，这次查找并不是查找一个组合就可以了，而是要找出所有可能的组合，也就是说后面这一部分算法的时间复杂度是固定的O(n)。然后就是去重复的问题，由于数组已经排序，那么当i扫描到两个相邻相同元素时则应跳过后面的相同元素，后面的lef和rig也是如此。
总之，这种题的算法思路和第一题有异曲同工之妙，考察的就是通过排序来降低原问题的时间复杂度，这就需要我们对快速排序比较了解，所以大家最好自己编写一下快速排序的算法，不要每次都用现成的标准库程序。
接下来一段时间会比较忙，可能会隔一段时间再回来继续写。这段时间心情依然不佳，希望早点儿好起来吧
