leetcode-3SUM（三数相加等于0）

转自leetcode-3SUM(三数相加等于0)
Given an array nums of n integers, are there elements a, b, c in nums 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.

Example:

Given array nums = [-1, 0, 1, 2, -1, -4],
 
A solution set is:
[
  [-1, 0, 1],
  [-1, -1, 2]]

Java 程序如下：

import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;
 
public class ThreeSum {
    public static List<List<Integer>> threeSum(int[] nums) {
        //先将数组进行升序排序
        Arrays.sort(nums);
        LinkedList result = new LinkedList();
        //先选择一个数，然后在后面的挑选两个元素求和，因此i < num.length - 2
        for(int i = 0; i < nums.length - 2; i++){
            //定义两个指针
            int lo,hi,sum;
            //当i=0时，意味着第一次遍历，当i>0时，若num[i]==num[i-1]，则可以跳过该元素（因为数组是有序的）
            if(i == 0 || nums[i] != nums[i-1]){
                //低位指针从i+1开始，避免重复元祖
                lo = i+1;
                //高位指针从最后一个元素开始
                hi = nums.length-1;
                while (lo < hi){
                    sum = 0 - nums[i];
                    if(sum == nums[lo]+nums[hi]){
                        result.add(Arrays.asList(nums[i],nums[lo],nums[hi]));
                        //若当前指针元素与移动方向上的下一个指针元素相同，则跳过（此处要做++（--）操作才能跳过）
                        while (lo<hi && nums[lo] == nums[lo+1]) {
                            lo++;
                        }
                        while (lo<hi && nums[hi] == nums[hi-1]) {
                            hi--;
                        }
                        lo++;
                        hi--;
                    }
                    //若两数之和小于0，则lo++；大于0则hi--
                    else if(nums[lo]+nums[hi] < sum) lo++;
                    else hi--;
                }
            }
        }
        return result;
    }
 
    public static void main(String[] args) {
        int[] nums= new int[]{-4,-2,-2,-2,0,1,2,2,2,3,3,4,4,6,6};
        System.out.println(Arrays.deepToString(threeSum(nums).toArray()));
    }
}