【leetcode】15. 3Sum

题目描述：

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.

解题分析：

这道题注意一下几点即可：

1，先固定前两个数的位置，移动第三个数，这样的查找方式不会有数字组合的遗漏；

2，要考虑到数组元素有重复的情况下的处理。

3，若先为数组排序（这类题一般都这么做）,要充分利用有序的特点来减少比较情况，优化代码。

具体代码：

 public class Solution {

    public static List<List<Integer>> threeSum(int[] nums) {

         List<List<Integer>> results = new ArrayList<List<Integer>>();

         //边界情况的判断

         if(nums.length<3){

             //results.add(new ArrayList<Integer>());

             return results;

         }

         if(nums.length==3){

             if(nums[0]+nums[1]+nums[2]==0){

                 List<Integer> array =new ArrayList<Integer>();

                 array.add(nums[0]);

                 array.add(nums[1]);

                 array.add(nums[2]);

                 results.add(array);

                 return results;

             }

             else{

                 //results.add(new ArrayList<Integer>());

                 return results;

             }

         }

         //先为数组排序

         Arrays.sort(nums);

         //先把前两个数确定，变第三个数得值，以保证查找了所有例子

         for(int i=0;i<nums.length-2;i++){

             //如果第一个数已经大于零，就没有必要再找下去了

             if(nums[i]>0)

             break;

             for(int j=i+1;j<nums.length-1;j++){

                 //同上

                 if(nums[i]+nums[j]>0)

                 break;

                 for(int index=j+1;index<nums.length;index++){

                     if(nums[i]+nums[j]+nums[index]==0){

                         List<Integer> array = new ArrayList<Integer>();

                         array.add(nums[i]);

                         array.add(nums[j]);

                         array.add(nums[index]);

                         results.add(array);

                         //避免结果重复的处理

                         while(index+1<nums.length && nums[index+1]==nums[index]){

                             index++;

                         }

                     }

                 }

                 //避免结果重复的处理

                 while(j+1<nums.length-1 && nums[j+1]==nums[j]){

                     j++;

                 }

             }

             //避免结果重复的处理

             while(i+1<nums.length-2 && nums[i+1]==nums[i]){

                 i++;

             }

         }

         return results;

     }

 }

巴特西

【leetcode】15. 3Sum

最新文章

热门文章