题目：
题目
解析：
简单来说，就是三个数相加等于0，找出所有的无重复的组合。
思路：
开始想的很简单，先把所有的的都找出来然后再进行去重复。然后具体实现起来，就只会用for循环来实现，简直宛如一只ZZ，哎……
代码：
class Solution {
public List<List<Integer>> threeSum(int[] nums) {
List<List<Integer>> result = new ArrayList<List<Integer>>();
if(nums.length == 0) return result;
for(int i =0;i<nums.length-2;i++){
for(int j =i+1;j<nums.length-1;j++){
for(int k =j+1;k<nums.length;k++){
List<Integer> threes = new ArrayList<Integer>();
int a1 = nums[i];
int a2 = nums[j];
int a3 = nums[k];
if(a1+a2+a3 == 0){
threes.add(a1);
threes.add(a2);
threes.add(a3);
result.add(threes);
}
}
}
}
//后面要对得到的result结果进行去重复
//这一句只是去除了完全相同的部分，但是没有去除元素相同顺序不同的部分
List<List<Integer>> norepeat = new ArrayList(new HashSet(result));
//下面进行彻底的去重复
loop: for(int i = norepeat.size()-1;i>0;i--){
List<Integer> g1 = norepeat.get(i);
for(int j = i-1;j>=0;j--){
List<Integer> g2 = norepeat.get(j);
for(int k = 0; k<3;k++){
int sum = 0;
if(g1.get(0)==g2.get(k)) {
sum++;
if(k==0){
if(g1.get(1)==g2.get(1)||g1.get(1)==g2.get(2)) sum++;
}else if(k==1){
if(g1.get(1)==g2.get(0)||g1.get(1)==g2.get(2)) sum++;
}else{
if(g1.get(1)==g2.get(1)||g1.get(1)==g2.get(0)) sum++;
}
}
if(sum>=2){
norepeat.remove(i);
continue loop;
}
}
}
}
return norepeat;
}
}
后记：
如上代码，肉眼可见的超时了，哭唧唧……都到最后两个测试用例了
但是想也知道，上述暴力算法中，三层for循环，时间复杂度为O(N^3)，然后还要处理重复的问题，必然会超时的，显然不是有效的解决办法。
超时
下面是一番折腾后，优化得到的submitted解法：
思路：
网上查询了一下后才知道，K sum问题是一个系列，以后可以总结思考，对于这道题，可以考虑通过先将数组排序，然后固定一个数，用两个指针分别从它后面的所有数中从前往后和从后往前扫描，将得到的两个数字之和等于该数的相反数放到结果集中，在判断时跳过相同的数字，这样就不会有重复的问题了。
代码：
public class Solution {
public List<List<Integer>> threeSum(int[] nums) {
List<List<Integer>> res = new ArrayList<List<Integer>>();
int len=nums.length;
if(len<3)return res;
//先把数组排序了，然后再对排序后的数组进行遍历
Arrays.sort(nums);
for(int i=0;i<len-2;i++){
if(nums[i]>0)break; //对有序增数组来说，第一个数大于零，后面不会有三数之和等于0的情况
if(i>0 && nums[i]==nums[i-1])continue; //相同的数，直接跳过
int begin=i+1,end=len-1;
while(begin<end){
int sum=nums[i]+nums[begin]+nums[end];
if(sum==0){
List<Integer> list = new ArrayList<Integer>();
list.add(nums[i]);list.add(nums[begin]);list.add(nums[end]);
res.add(list);
begin++;end--;
while(begin<end && nums[begin]==nums[begin-1])begin++;
while(begin<end && nums[end]==nums[end+1])end--;
}else if(sum>0)end--;
else begin++;
}
}
return res;
}
}
