题目：三数之和
内容：
给定一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？找出所有满足条件且不重复的三元组。
注意：答案中不可以包含重复的三元组。
例如, 给定数组 nums = [-1, 0, 1, 2, -1, -4]， 满足要求的三元组集合为：
[
[-1, 0, 1],
[-1, -1, 2]
]
思路：
题目实现可分为两个步骤，分别是（1）寻找三个满足条件的元素（2）去重复
对于第一个小问题，首先考虑三个for循环，直接寻找
1.第一个数字(num1)选取范围1~n
2.第二个数字(num2)选取范围num1+1~n
3.第三个数字(num3)选取范围num2+1~n
代码如下：
//寻找三数之和为0的数 C++
vector<int> vec();
unsigned int num1 = , num2 = , num3 = ;
for (num1; num1 < nums.size() - ; num1++){
for (num2 = num1 + ; num2 < nums.size() - ; num2++){
for (num3 = num2 + ; num3 < nums.size(); num3++){
if (nums[num1] + nums[num2] + nums[num3] == ){
vec[] = nums[num1];
vec[] = nums[num2];
vec[] = nums[num3];
vecs.push_back(vec);
}
}
}
}
第二个小问题去重复
C++ 的STL提供有去重算法unique，直接去重即可
1.在寻找满足条件的三个数字之前要先排序，防止相同的vec因为内部元素顺序不同去不了重复，如[1,2,3]和[2,1,3]会判定为不重复
2.对于vecs结果进行去重，去重之前一定要再次排序，因为unique函数只是比较相邻的两个元素是否重复，如果重复就将重复的放到尾部，如果不限排序，对于vecs[[1,2,3],[0,0,0],[1,2,3]]，因为相邻的元素都不想等（[1,2,3]≠[0,0,0]），系统会去重失败
去重代码如下:
//先排序，方便去重
sort(nums.begin(), nums.end());
//寻找三个满足条件的数字代码省略。。。。
//去重
sort(vecs.begin(), vecs.end());
vecs.erase(unique(vecs.begin(), vecs.end()), vecs.end()); return vecs;
此外，还要考虑异常的情况，当传入的数组长度小于3时，无法给出满足条件的解，应返回空的容器
完整代码如下:
vector<vector<int>> threeSum(vector<int>& nums) {
vector<vector<int>> vecs;
//异常判断
if (nums.size() < )
return vecs;
//先排序，方便去重
sort(nums.begin(), nums.end());
//寻找三数之和为0的数
vector<int> vec();
unsigned int num1 = , num2 = , num3 = ;
for (num1; num1 < nums.size() - ; num1++){
for (num2 = num1 + ; num2 < nums.size() - ; num2++){
for (num3 = num2 + ; num3 < nums.size(); num3++){
if (nums[num1] + nums[num2] + nums[num3] == ){
vec[] = nums[num1];
vec[] = nums[num2];
vec[] = nums[num3];
vecs.push_back(vec);
}
}
}
}
//去重
sort(vecs.begin(), vecs.end());
vecs.erase(unique(vecs.begin(), vecs.end()), vecs.end());
return vecs;
}
对于较短的输入，能给出合适的结果，然后对于巨长的数组，系统提示运算时间过长，因此需要优化代码。
根据题目所给的条件，可以看出三个数字之和是定值，因此，当我们选取第一个数字num1后，问题变为寻找和为0-num1的两个数字。
可以观察到，因为数组是有序的，我们可以设置两个指针从两边同时选取
int targetSum = - nums[num1];
while (pLeft < pRight ){
int sum = nums[pLeft] + nums[pRight];
if (sum > targetSum || nums[pRight] == nums[pRight-]){
pRight--;
}
else if (sum < targetSum || nums[pLeft] == nums[pLeft - ]){
pLeft++;
}
else{
vec[] = nums[num1];
vec[] = nums[pLeft];
vec[] = nums[pRight];
vecs.push_back(vec);
pLeft++;
pRight--;
}
}
也因为数组是排序的，为了如果我们选取的第一个数子大于0，则后两个必然大于0，可以跳出循环
对于重复的数字，我们可以选择跳过
完整代码如下：
vector<vector<int>> threeSum(vector<int>& nums) {
vector<vector<int>> vecs;
//异常判断
if (nums.size() < )
return vecs;
//先排序，方便去重
sort(nums.begin(), nums.end());
//寻找三数之和为0的数
vector<int> vec();
unsigned int num1 = , num2 = , num3 = ;
for (num1; num1 < nums.size() - ; num1++){
if (nums[num1] * > )//数组是从小到大排序
break;
if (num1 != && nums[num1] == nums[num1 - ])
continue;
int pLeft, pRight;
pLeft = num1+;
pRight = nums.size() - ;
int targetSum = - nums[num1];
while (pLeft < pRight ){
int sum = nums[pLeft] + nums[pRight];
if (sum > targetSum || nums[pRight] == nums[pRight-]){
pRight--;
}
else if (sum < targetSum || nums[pLeft] == nums[pLeft - ]){
pLeft++;
}
else{
vec[] = nums[num1];
vec[] = nums[pLeft];
vec[] = nums[pRight];
vecs.push_back(vec);
pLeft++;
pRight--;
}
}
}
//去重
sort(vecs.begin(), vecs.end());
vecs.erase(unique(vecs.begin(), vecs.end()), vecs.end());
return vecs;
}
对于复杂测试案例的运行时间是60ms，通过题目！