3sum(从数组中找出三个数的和为0)

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: 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]

]

从上面可以看出，这样的结果可能出现多个。而且还有重复数字出现。。

我们知道求两个数的和，可以先排序，然后两端向中间找，如果求下标，则用hashmap。

这里不是求下标，所以不需要使用hashmap。

思路就是：先排序，然后遍历数组，当前元素nums[i],，并从剩下的数组中找两个数的和0-nums[i]，这个做法就是两边向中间找。需要注意，排序过后会有重复元素，在外层遍历的时候，我们要跳过重复元素（当前元素和前一个相同）。在内部遍历查找两个数的和时，也要跳过重复元素（如果当前符合要求的值刚好是重复的，就跳过那些重复的，只要计算一遍就行）。具体的跳过重复的步骤见代码。。

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

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

        if(nums==null||nums.length<3) return result;

        Arrays.sort(nums);

        List<Integer> list;

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

            //跳过重复的,这个跟前一个不一样就进行

            if(i==0||(i>0&&nums[i]!=nums[i-1])){

                //开始从剩下的数组中查找和为0-nums[i]的两个数,而且是要遍历完剩下所有元素，因为可能存在多组

                int left=i+1,right=nums.length-1,sum=0-nums[i];

                while(left<right){

                    if(nums[left]+nums[right]==sum){

                        //找到一组了，加到集合中

                       list=new ArrayList<>();

                        list.add(nums[i]);list.add(nums[left]);list.add(nums[right]);

                        result.add(list);

                        //跳过重复元素。这里跳到了重复节点的最后一个，也就是说还需要在++

                        while(left<right&&nums[left+1]==nums[left]) left++;

                        while(left<right&&nums[right]==nums[right-1]) right--;

                        left++;right--;

                    }else if(nums[left]+nums[right]<sum){

                        left++;

                    }else right--;

                }

            }

        }

        return result;

    }

巴特西

3sum(从数组中找出三个数的和为0)

最新文章

热门文章