面试题7：数组中和为0的3个数字（Java版）

题目：输入一个数组，如何找出数组中所有和为0的3个数字的
三元组？需要注意的是，返回值中不得包含重复的三元组。例如，
在数组[-1，0，1，2，-1，-4]中有两个三元组的和为0，它们分别
是[-1，0，1]和[-1，-1，2]。

//首先将数组排序
//固定一个固定指针i然后右移指针j和左移指针k
// j的初始位置在最开头，k的初始位置在最末尾
public List> threeSum(int[] nums) {
    List> result = new LinkedList>();
    if (nums.length >= 3) {
        Arrays.sort(nums);
        int i = 0;
        //因为是三元组所以i需要小于数组长度减2
        while(i < nums.length - 2) {
            twoSum(nums, i, result);
            int temp = nums[i];
            //因为不能出现重复三元组，所以重复的nums[i]直接跳过
            while (i < nums.length && nums[i] == temp) {
                ++i;
            }
        }
    }
    return result;
}

//当i固定后移动j，k指针
public void twoSum(int[] nums, int i,List> result) {
    int j = i + 1;
    int k = nums.length - 1;
    while (j < k) {
        if (nums[i] + nums[j] + nums[k] == 0) {
            result.add(Arrays.asList(nums[i], nums[j], nums[k]));
            int temp = nums[j];
            //因为不能出现重复三元组，所以重复的nums[j]直接跳过
            while (temp == nums[j] && j < k) {
                ++j;
            }
        } else if (nums[i] + nums[j] + nums[k] < 0) {
            ++j;
        } else {
            --k;
        }
    }
}