Q15 三数之和

思路

我的思路，先排序，循环确定前两个值，最后一个值二分

看了题解：
最后两个值可以使用双指针，因为是有序的，而且是求和

注意重复值：

 public List<List<Integer>> threeSum(int[] nums) {
        Arrays.sort(nums);
        List<List<Integer>> resultList = new ArrayList<>();
        for (int i = 0; i < nums.length-2; i++) {
            if (i!=0 && nums[i] == nums[i-1]){
                continue;
            }
            resultList.addAll(twoSum(i+1, nums[i],nums));
        }
        return resultList;
    }

    private List<List<Integer>> twoSum(int index, int first, int[] nums) {
        List<List<Integer>> resultList = new ArrayList<>();
        int left = index;
        int right = nums.length-1;
        while (left<right){
            if (nums[left] + nums[right] + first == 0){
                List<Integer> list = new ArrayList<>(3);
                list.add(first);
                list.add(nums[left]);
                list.add(nums[right]);
                resultList.add(list);

                left = findNext(left,nums);
            } else if (nums[left] + nums[right] +  first >0) {
                right--;
            }else {
                left++;
            }
        }
        return resultList;
    }

    //避免出现重复，如果右移和右边一样
    private int findNext(int left, int[] nums) {
        int index = left+1;
        while (index < nums.length &&nums[index] == nums[left]){
            index++;
        }
        return index;
    }
    ```
    
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44