leetcode 15 Solution

代码解析

package com.demo.s15;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * 三数之和
 * 给你一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？请你找出所有和为 0 且不重复的三元组。
 *
 * 注意：答案中不可以包含重复的三元组。
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode.cn/problems/3sum
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        //结果list
        List ret = new ArrayList();
        //判断入参
        if(nums.length < 3) return ret;
        //排序数据，方便设置左右边界 遍历
        Arrays.sort(nums);
        //先定义一个元素遍历，作为三个中最小的一个值
        for(int i = 0 ;i< nums.length-2; i++) {
            //判断终止条件
            if(nums[i] > 0)  return ret;
            //忽略到相同的值
            if(i> 0 && nums[i] == nums[i-1]) continue;
            //第二个元素 取区间左边界
            int L = i +1;
            //第三个元素 取区间右边界
            int R = nums.length - 1;
            //如果左右边界重合 则停止
            while(L < R) {
                //如果三数和为0
                if(nums[i] + nums[L] + nums[R] == 0) {
                    //记录三个数
                    List numbers = new ArrayList();
                    numbers.add(nums[i]);
                    numbers.add(nums[L]);
                    numbers.add(nums[R]);
                    ret.add(numbers);
                    //基于已有的和为0 左右移动边界 寻找其他的记录
                    while(L< R && (nums[L] == nums[L+1])) {
                        //忽略相同的数值 左边界右移
                        L++;
                    }
                    while(R > L && nums[R] == nums[R-1]) {
                        //忽略相同的数值 右边界左移
                        R--;
                    }
                    //移动左右边界
                    L++;
                    R--;
                } else if(nums[i] + nums[L] + nums[R] < 0) {
                    // 和小于0  左边界右移
                    L++;
                } else {
                    // 和大于0  右边界左移
                    R--;
                }
            }
        }
        return ret;
    }
}