你的位置:首页 > Java教程

[Java教程]15. 3Sum


Given an array S of n integers, are there elements abc 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 }