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)
解题思路：
3Sum对初学者估计是丈二和尚摸不着头脑，其实NSum都有固定的解法。参考链接：
http://tech-wonderland.net/blog/summary-of-ksum-problems.html
基本上所有思路都是排序后查找，防止出现List的重复，因此想到使用set类型，JAVA实现如下：
static public List<List<Integer>> threeSum(int[] num) {
LinkedHashSet<List<Integer>> set = new LinkedHashSet<List<Integer>>();
if (num.length <= 2)
return new ArrayList<List<Integer>>(set);
final int tar = 0;
Arrays.sort(num);
for (int i = 0; i < num.length - 2; i++) {
int j = i + 1, k = num.length - 1;
while (j < k) {
if (num[i] + num[j] + num[k] < tar)
j++;
else if (num[i] + num[j] + num[k] > tar)
k--;
else {
set.add(Arrays.asList(num[i], num[j], num[k]));
j++;
k--;
}
}
}
return new ArrayList<List<Integer>>(set);
}
结果第一次提交Time Limit Exceeded，第二次提交竟然神奇般的通过了！！！时间425ms，估计也是擦线飘过。
原因在于set每添加一个元素都会和set中元素进行比较，也就是说需要一次遍历，这样每添加一个元素，时间开销就会比较大，因此修改代码如下，时间322 ms：
static public List<List<Integer>> threeSum(int[] num) {
ArrayList<List<Integer>> list = new ArrayList<List<Integer>>();
final int tar = 0;
Arrays.sort(num);
for (int i = 0; i < num.length - 2; i++) {
int j = i + 1, k = num.length - 1;
while(i < k && num[i]==num[i+1])
i++;
while (j < k) {
if (num[i] + num[j] + num[k] < tar)
j++;
else if (num[i] + num[j] + num[k] > tar)
k--;
else {
list.add(Arrays.asList(num[i], num[j], num[k]));
j++;
k--;
while(j<k&&num[j]==num[j-1])
j++;
while(k>j&&num[k]==num[k+1])
k--;
}
}
}
return list;
}
C++：
class Solution {
public:
vector<vector<int>> threeSum(vector<int>& nums) {
vector<vector<int>> res;
if (nums.size() <= )
return res;
const int tar = ;
sort(nums.begin(),nums.end());
for (int i = ; i < nums.size() - ; i++) {
int j = i + , k = nums.size() - ;
while (i < k && nums[i] == nums[i + ])
i++;
while (j < k) {
if (nums[i] + nums[j] + nums[k] < tar)
j++;
else if (nums[i] + nums[j] + nums[k] > tar)
k--;
else {
res.push_back({ nums[i], nums[j], nums[k]});
j++;
k--;
while (j<k&&nums[j] == nums[j - ])
j++;
while (k>j&&nums[k] == nums[k + ])
k--;
}
}
}
return res;
}
};