leetcode题目15. 三数之和（java）

题目描述

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

示例

给定数组 nums = [-1, 0, 1, 2, -1, -4]，满足要求的三元组集合为：
[
  [-1, 0, 1],
  [-1, -1, 2]
]

代码

public List<List<Integer>> threeSum(int[] nums) {
    List<List<Integer>> lists = new ArrayList<>();
    //排序
    Arrays.sort(nums);

    int len = nums.length;
    for(int i = 0;i < len;++i) {
        // 因为已经排序好，所以后面不可能有三个数加和等于 00，直接返回结果。
        if(nums[i] > 0) return lists;
        // 对于重复元素：跳过，避免出现重复解
        if(i > 0 && nums[i] == nums[i-1]) continue;

        int curr = nums[i]; // 以curr 为三个数的一个数，在i后面的数字中找另外两个数
        int L = i+1, R = len-1; // L和R分别为左右指针，在L和R之间找另外两个数字
        while (L < R) {
            int tmp = curr + nums[L] + nums[R];
            if(tmp == 0) {
                // 找到了符合条件的数
                List<Integer> list = new ArrayList<>();
                list.add(curr);
                list.add(nums[L]);
                list.add(nums[R]);
                lists.add(list);
                // 就寻找下一个组符合条件的值
                while(L < R && nums[L+1] == nums[L]) {
                    ++L;
                }
                while (L < R && nums[R-1] == nums[R]) {
                    --R;
                }
                ++L;
                --R;
            } else if(tmp < 0) {
                ++L;
            } else {
                --R;
            }
        }
    }
    return lists;
}