15. 三数之和

1.题目描述

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

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

示例 1：

输入：nums = [-1,0,1,2,-1,-4]
输出：[[-1,-1,2],[-1,0,1]]

示例 2：

输入：nums = []
输出：[]

示例 3：

输入：nums = [0]
输出：[]

2.解题过程

1.暴力解法

最简单的方式，三层for循环，编写代码验证后会发现结果中有重复的三元组，这里先对数组进行排序，在循环的过程中遇到相同的数值，直接跳过

class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        int len = nums.length;
        List<List<Integer>> result = new ArrayList<List<Integer>>();
        if (len < 3) {
            return result;
        }

        Arrays.sort(nums);
        for (int i = 0; i < len; i++) {
            if (i > 0 && (nums[i] == nums[i-1])) {
                continue;
            }
            int target = -nums[i];
            for (int j = i+1; j < len; j++) {
                if (j > i+1 && (nums[j] == nums[j-1])) {
                    continue;
                }
                for (int k = j+1; k < len; k++) {
                    if (k > j+1 && (nums[k] == nums[k-1])) {
                        continue;
                    }
                    if ((nums[j] + nums[k] == target)) {
                        Integer[] rowData = {nums[i], nums[j], nums[k]};
                        result.add(Arrays.asList(rowData));
                    }
                }
            }
        }
        return result;
    }
}

2.双指针

在暴力解法中我们为了去重，对数组进行了排序，数值默认按照从小到大排列。为了求两数之和，我们可以设置首尾两个指针，通过左右指针滑动，来不断接近预期值，当两个指针相遇时退出遍历

class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        int len = nums.length;
        List<List<Integer>> result = new ArrayList<List<Integer>>();
        if (len < 3) {
            return result;
        }

        Arrays.sort(nums);
        for (int i = 0; i < len; i++) {
            if (i > 0 && (nums[i] == nums[i-1])) {
                continue;
            }
            int target = -nums[i];
            int left = i + 1;
            int right = len - 1;
            while (left < right) {
                if (left > i + 1 && nums[left] == nums[left-1]) {
                    left++;
                    continue;
                }
                if (right < len - 1 && nums[right] == nums[right+1]) {
                    right--;
                    continue;
                }
                if (nums[left] + nums[right] == target) {
                    Integer[] resultItem = {nums[i], nums[left], nums[right]};
                    result.add(Arrays.asList(resultItem));
                    left++;
                    right--;
                } else if (nums[left] + nums[right] < target) {
                    left++;
                } else {
                    right--;
                }
            }
        }
        return result;
    }
}