【萌新解题】三数之和

class Solution {    public List<List<Integer>> threeSum(int[] nums) {        //按照题目要求，是求和0的三元组，所以target传0即可        return threeSum(nums, 0);    }
    /**     * 三数之和     * 在数组nums中找出所有和等于target的不重复三元组     */    public List<List<Integer>> threeSum(int[] nums, int target) {        // 首先对数组排序，这是一切的前提        Arrays.sort(nums);
        // 数组长度        int len = nums.length;
        // 结果集合        List<List<Integer>> ans = new ArrayList<>();        // 结果集合中的某一个三元组        List<List<Integer>> tmp = null;
        for (int i = 0; i < len; ++i) {            // 固定nums[i]作为第一个元素，通过twoSum得到所有满足条件的另外两个元素            // 然后一起组成一个三元组，注意，twoSum 入参中，数组开始的下标start要设置            // 为i+1，不能再包含 nums[i]            tmp = twoSum(nums, i + 1, target - nums[i]);            for (List<Integer> item : tmp) {                item.add(nums[i]);                // 找到符合条件的一个三元组，并添加到结果结合中                ans.add(item);            }
            // 当出现类似 [1,1,2,2,2,3,3] 这样有重复元素的数组时，要跳过重复元素            while (i < len - 1 && nums[i] == nums[i + 1]) {                ++i;            }        }        return ans;    }
    /**     * 两数之和     * 输入数组nums已经排好序，无需重复排序，且下标从start开始     * 也就是找出从start开始到nums.length之间，所有满足和为target的不重复二元组     */    public List<List<Integer>> twoSum(int[] nums, int start, int target) {        // TODO    }}

public class Solution {    /**     * 两数之和     * 输入数组nums已经排好序，无需重复排序，且下标从start开始     * 也就是找出从start开始到nums.length之间，所有满足和为target的不重复二元组     */    public List<List<Integer>> twoSum(int[] nums, int start, int target) {        // 数组长度        int len = nums.length;
        // 左指针，指向数组开头        int left = start;
        // 右指针，指向数组尾部        int right = len - 1;
        // 返回结果        List<List<Integer>> ans = new ArrayList<>();
        // 开始循环        while (left < right) {            int sum = nums[left] + nums[right];
            // 保存当前循环的第一个数，后面用于判重            int numLeft = nums[left];
            // 保存当前循环的第二个数，后面用于判重            int numRight = nums[right];
            if (target == sum) {                // 找到目标元素，保存到结果集中                List<Integer> tmp = new ArrayList<>();                tmp.add(nums[left]);                tmp.add(nums[right]);                ans.add(tmp);
                // 当出现类似 [1,1,2,2,2,3,3] 这样有重复元素的数组时，要跳过重复元素                // 因为题目要求结果集合不重复                while (left < right && nums[left] == numLeft) {                    left++;                }
                // 当出现类似 [1,1,2,2,2,3,3] 这样有重复元素的数组时，要跳过重复元素                // 因为题目要求结果集合不重复                while (left < right && nums[right] == numRight) {                    right--;                }            } else if (target < sum) {                // 当出现类似 [1,1,2,2,2,3,3] 这样有重复元素的数组时，要跳过重复元素                // 减少不必要的循环                while (left < right && nums[right] == numRight) {                    right--;                }            } else if (target > sum) {                // 当出现类似 [1,1,2,2,2,3,3] 这样有重复元素的数组时，要跳过重复元素                // 减少不必要的循环                while (left < right && nums[left] == numLeft) {                    left++;                }            }        }
        return ans;    }}