57.3Sum-三数之和

Description

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.

(-1, 0, 1)
(-1, -1, 2)

Solution

解题思路：将Three-Sum的问题转换为Two-Sum的问题

1. 上来先排序

2. 将a + b + c = 0 Three-Sum的问题转换为 -a = b + c Two-Sum的问题

3. 循环小的那个数a（如果重复就跳过），并在剩下的区间里寻找和为-a的target，这道题中剩下的区间就是i + 1到nums.length - 1;

注意：

1. 排序。这种题上来先看是否有序，无序的话要先排序。

2. 去除重复。通过比较前后是否相等的方式来去除重复，如果前后相同，则指针继续跳，直到找到不同元素为止。

public class Solution {
    /**
     * @param numbers: Give an array numbers of n integer
     * @return: Find all unique triplets in the array which gives the sum of zero.
     */
    public List> threeSum(int[] numbers) {
        // write your code here
        //1. 上来先排序
        //2. 将a + b + c = 0 3-Sum的问题转换为 -a = b + c Two-Sum的问题
        //3. 循环小的那个数a（如果重复就跳过）在剩下的区间里寻找和为-a的target
        
        List> results = new ArrayList<>();
        if (numbers == null || numbers.length <3) {
            return results;
        }
        
        Arrays.sort(numbers);
        for (int i = 0; i  0 && numbers[i] == numbers[i - 1]) {
                continue;
            }
            int left = i + 1, right = numbers.length - 1;
            int target = -numbers[i];
            twoSum(numbers, left, right, target, results);
        }
        return results;
    }
    private void twoSum(int[] nums,
                        int left,
                        int right,
                        int target,
                        List> results) {
        while (left  triple = new ArrayList<>();
                triple.add(-target);
                triple.add(nums[left]);
                triple.add(nums[right]);
                results.add(triple);
                left++;
                right--;
                
                //跳过重复元素
                while (left