15. 三数之和

思路：

• 首先对数组进行排序,排序后,依次固定一个数nums[i],再使用左右指针指向nums[i]后面的两端,数字分别为 nums[L] 和 nums[R]，计算三个数的和 sum 判断是否满足为 0，满足则添加进结果集
• 如果nums[i]大于0,则三数之和必然无法等于0,结束循环
• 如果nums[i]==nums[i-1],则说明该数字重复,会导致结果重复,所以应该跳过
• 当sum=0时,nums[l]=nums[L+1]则会导致结果重复,应该跳过,L++
• 当sum==0时,nums[R]==nums[R-1]则会导致结果重复,应该跳过,R--
• 时间复杂度:O(n2),n为数组长度

代码：

 public List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> res = new LinkedList<>();
        int length = nums.length;
        if (length < 1) {
            return res;
        }
        //a=-(b+c)
        Arrays.sort(nums);
        for (int i = 0; i < length; i++) {
            if (nums[i] > 0) {
                // 如果当前数字大于0，则三数之和一定大于0，所以结束循环
                break;
            }
            //相同比较点已经比较过了，不需要再次比较
            if (i > 0 && nums[i] == nums[i - 1]) {
                continue;
            }

            int l = i + 1;
            int r = length - 1;
            while (l < r) {
                int sum = nums[l] + nums[r] + nums[i];
                if (sum == 0) {
                    res.add(Arrays.asList(nums[i], nums[l], nums[r]));
                    //去除相同数字结果，避免多次循环
                    while (l < r && nums[l] == nums[l + 1]) {
                        l++;
                    }
                    while (r > l && nums[r] == nums[r - 1]) {
                        r--;
                    }
                    l++;
                    r--;
                } else if (sum < 0) {
                    l++;
                } else if (sum > 0) {
                    r--;
                }
            }

        }

        return res;
    }