【题目】
3Sum Total Accepted: 6032 Total Submissions: 35898My Submissions
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:
Elements in a triplet （a,b,c） must be in non-descending order. （ie, a ≤ b ≤ c）
The solution set must not contain duplicate triplets.
For example, given array S = {-1 0 1 2 -1 -4},
A solution set is:
（-1, 0, 1）
（-1, -1, 2）
Discuss
【题意】
给定n个整数的数组S,是否在 数组S中有元素a,b,C,使得A + B + C =0 在数组中找出独一无二的三元素组，使得他们之和为0.
注意：
在三元素组（A,B,C）中，必须满足非递减排序。 （即A≤B≤C）
该解决方案集中一定不能包含重复的三元素组。
【分析】
先排序，然后二分查找，复杂度 O（n^2*log n）。a + b + c = 0 即 b + c = -a
题目思路与 剑指Offer之和为S的连续正数序列 博文思路一致。可以参考一下解题思路。
另有：点击打开链接 详细总结
【代码】
/*********************************
* 日期：2014-01-18
* 作者：SJF0115
* 题号： 3Sum
* 来源：http://oj.leetcode.com/problems/3sum/
* 结果：AC
* 来源：LeetCode
* 总结：
**********************************/
#include
#include
#include
#include
using namespace std;
class Solution {
public:
vector > threeSum（vector &num） {
int i,j,target,start,end;
int Len = num.size（）；
vector triplet;
vector> triplets;
//排序
sort（num.begin（），num.end（））；
for（i = 0;i < Len-2;i++）{
//跳过重复元素
if（i != 0 && num[i] == num[i-1]）{
continue;
}
//a + b + c = 0
target = -num[i];
//二分查找
start = i + 1;
end = Len - 1;
while（start < end）{
int curSum = num[start] + num[end];
//相等 -> 目标
if（target == curSum）{
triplet.clear（）；
triplet.push_back（num[i]）；
triplet.push_back（num[start]）；
triplet.push_back（num[end]）；
triplets.push_back（triplet）；
//注意： 跳过重复元素
while（start < end && num[start] == num[start + 1]）{
start ++;
}
while（start < end && num[end] == num[end - 1]）{
end --;
}
start ++;
end --;
}
//大于 -> 当前值小需要增大
else if（target > curSum）{
//注意：跳过重复元素
while（start < end && num[start] == num[start + 1]）{
start ++;
}
start ++;
}
//小于 -> 当前值大需要减小
else{
//注意：跳过重复元素
while（start < end && num[end] == num[end - 1]）{
end --;
}
end --;
}
}//while
}//for
return triplets;
}
};
int main（） {
vector> result;
Solution solution;
vector vec;
vec.push_back（-2）；
vec.push_back（0）；
vec.push_back（0）；
vec.push_back（2）；
vec.push_back（2）；
result = solution.threeSum（vec）；
for（int i = 0;i < result.size（）；i++）{
for（int j = 0;j < result[i].size（）；j++）{
printf（"%d ",result[i][j]）；
}
printf（"\n"）；
}
return 0;
}
【测试】
Input: [-2,0,0,2,2]
Expected: [[-2,0,2]] |