首页 > 代码库 > Leetcode 3Sum

Leetcode 3Sum

2024-08-09 21:23:02   218人阅读

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）num为null
2）num中元素个数小于三个
对于上面两个特殊情况，应单独拎出来考虑，
接着对数组进行排序，然后固定一个数字，其他两个数字相加的和为这个数字的相反数，同时要考虑，a,b,c的重复情况
 1 package san.Sum; 2  3 import java.util.ArrayList; 4 import java.util.Arrays; 5 import java.util.List; 6  7 public class Sum31 { 8  9     /**10      * @param args11      */12     public static void main(String[] args) {13         // TODO Auto-generated method stub14        int num[]={-2,0,1,1,2};15        List<List<Integer>> result=ThreeSum(num);16     }17     public static List<List<Integer>> ThreeSum(int[] num){18         //a+b+c=019         //b+c=-a20         if(num==null){21             return null;22         }23         int len=num.length;24         //首先对数组进行排序25         Arrays.sort(num);26         //再建一个List用来保存结果集27         List<List<Integer>> list=new ArrayList<List<Integer>>();28         //如果数组个数小于3，则直接装到list中返回29         if(len<3){30             return list;31         }32         //如果num中的元素个数大于3个，就需要筛选了33         //先固定一个，使另外两个的和为这个数的相反数，这里i为a34         for(int i=0;i<=len-3;i++){35             int a=num[i];36             int target=-a;37             //j=b,k=c需要保持j<k38             int j=i+1;39             int k=len-1;40             //当j<K的时候就不停地尝试41             while(j<k){42                 int tempSum=num[k]+num[j];43                 //如果计算出来的值比要求的值小，就让b增加,如果计算出来的值比要求的大，就让c减少44                 if(tempSum<target){45                     j++;46                 }else if(tempSum>target){47                     k--;48                 }else{49                     List<Integer> temp=new ArrayList<Integer>();50                     temp.add(num[i]);51                     temp.add(num[j]);52                     temp.add(num[k]);53                     list.add(temp);54                     j++;55                     k--;56                     //去重，防止这个j和上个j相同57                     while(j<len&&num[j]==num[j-1]){58                         j++;59                     }60                     //去重，防止这个k和上一个k相同61                     while(k>0&&num[k]==num[k+1]){62                         k--;63                     }64                 }65             }66             //去重，防止下一个i和这个i的值一样67             while(i<len-2&&num[i+1]==num[i]){68                 i++;69             }70         }71         return list;72     }73 74 }

 

 

Leetcode 3Sum


联系
我们