15. 3Sum，153sum

15. 3Sum，153sum

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)
代碼如下：（超時）

 1 public class Solution {
 2     public List<List<Integer>> threeSum(int[] nums) {
 3         List<List<Integer>> list1=new ArrayList<>();
 4         List<Integer> list=new ArrayList<>();
 5         Map<List<Integer>,List<Integer>> map=new HashMap<>();
 6         int a=0;
 7 
 8         Arrays.sort(nums);
 9 
10         for(int i=0;i<=nums.length-3;i++)
11         {
12             if(nums[i]<=0)
13             {
14                 list.add(nums[i]);
15                 a=nums[i]*(-1);
16             }
17             else break;
18             for(int j=i+1;j<=nums.length-2;j++)
19             {
20                 if(nums[j]<=a)
21                 {
22                     list.add(nums[j]);
23                     a=a-nums[j];
24                     for(int k=j+1;k<=nums.length-1;k++)
25                     {
26                          if(nums[k]>a)
27                              break; 
28                          else if(nums[k]==a)
29                         {
30                             list.add(nums[k]);
31                             if(!map.containsKey(list))
32                             {
33                                 map.put(list, list);
34                                 list1.add(list);
35                             }
36                             break;
37                         }
38                        
39                     }
40                 }
41                 else break;
42                 list=new ArrayList<>();
43                 list.add(nums[i]);
44                 a=nums[i]*(-1);
45             }
46             list=new ArrayList<>();
47         }
48      
49         return list1;
50     }
51 }