三数之和

题目：三数之和

要求：给你一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？请你找出所有满足条件且不重复的三元组。

注意：答案中不可以包含重复的三元组。

例如 ：
输入：[-1, 0, 1, 2, -1, -4]，
输出：[[-1, 0, 1],[-1, -1, 2]]

解题思路：

1. 对给定的数组排序，再使用双指针找出与当前数相加和为0的数
2. 对于已经排序的数组而言，在0之和不会再有与之相加和为0的两个数
3. 在遍历中，应判断当前数、左指针和右指针的下一位是否与当前相等，避免出现重复解

题解代码如下：

class Solution {
    private List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> result = new ArrayList<>();
        if (null == nums || nums.length < 3) {
            return result;
        }
        // 排序
        Arrays.sort(nums);
        int len = nums.length;
        for (int i = 0; i < len; i++) {
            int temp = nums[i];
            // 对于当前已排好序的数组来说，0后面的数字不可能出现三个数相加等于0
            if (temp > 0) {
                return result;
            }
            // 跳过重复元素，可以避免出现重复解
            if (i > 0 && temp == nums[i - 1]) {
                continue;
            }
            int left = i + 1;
            int right = len - 1;
            while (left < right) {
                int leftNum = nums[left];
                int rightNum = nums[right];
                int sum = temp + leftNum + rightNum;
                if (sum == 0) {
                    result.add(Arrays.asList(temp, leftNum, rightNum));
                    // 如果当前左指针与右指针是否和下一位相同，去除重复解
                    while (left < right && leftNum == nums[left + 1]) {
                        left ++;
                    }
                    while (left < right && rightNum == nums[right - 1]) {
                        right --;
                    }
                    left ++;
                    right --;
                } else if (sum < 0) {
                    left ++;
                } else {
                    right --;
                }
            }
        }
        return result;
    }
}