LeetCode15. 三数之和

LeetCode15. 三数之和

题目描述

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

思路分析

1. 使用排序加双指针的思路
2. 将排好序的数组元素使用双层遍历筛选满足条件的元素
3. 定义first、second、third三个指针分别指向数组元素的三个索引
4. 外层循环遍历数组中的每一个元素，考虑去重机制，即如果外层元素有连续一样的数字，则直接跳过
5. 内层循环负责查找剩下的不重复的两个数，second和third指针分别指向第一个元素右侧数组的第一个和最后一个元素的索引，然后遍历索引之间的所有元素，如果满足条件，则加入集合中

源码即详解

//思路分析
    //1. 将数组中的元素按照从小到大或者从大到小排序
    //2. 此题主要难点在于元素的去重
    //3. 取排序后数组中最小的一个数为参考点，然后取这个数右边的数组的左右两端的元素
    //4.  假如参考点这个数大于零，说明三数之和肯定大于0，结束
    //5.  否则移动指针判断有没有三数之和=0的，如果有，则加入集合
    //6.  去重：如果参考点右边的数和它相等，则结束，会重复
    //         如果左右指针移动后他们旁边的元素和它相等，结束
    //7.  关于指针移动，每次移动一个指针，如果和>0,移动右边指针，如果和<0,移动左边指针


public List<List<Integer>> threeSum(int[] nums) {
        //定义变量保存数组的长度
        int len = nums.length;
        //数组元素排序
        Arrays.sort(nums);
        //定义集合保存满足条件的三个数据
        List<List<Integer>> lists = new ArrayList<List<Integer>>();
        // 从左到右依次遍历数组元素
        //first为数组最左侧元素的指针
        for (int first = 0; first < len; ++first) {
            // 保证元素的不重复
            if (first > 0 && nums[first] == nums[first - 1]) {
                continue;
            }
            // third 对应的指针初始指向数组的最右端
            int third = len - 1;
            // 第二个元素和第三个元素和为target即可
            int target = -nums[first];
            // 第二个元素从第一个元素右侧开始遍历
            for (int second = first + 1; second < len; second++) {
                // 保证元素的不重复
                if (second > first + 1 && nums[second] == nums[second - 1]) {
                    continue;
                }
                // 需要保证 second 的指针在 third 的指针的左侧
                while (second < third && nums[second] + nums[third] > target) {
                    third--;
                }
                //如果两指针相等，则结束循环
                if (second == third) {
                    break;
                }
                //每循环一次，如果条件满足，则添加元素到集合
                if (nums[second] + nums[third] == target) {
                    List<Integer> list = new ArrayList<Integer>();
                    list.add(nums[first]);
                    list.add(nums[second]);
                    list.add(nums[third]);
                    lists.add(list);
                }
            }
        }
        return lists;
    }

下边解法抛出了越界异常

public List<List<Integer>> threeSum2(int[] nums) {
        //定义集合保存返回的元素
        ArrayList<List<Integer>> lists = new ArrayList<>();
        ArrayList<Integer> list = new ArrayList<>();
        //先进行数据校验
        if (nums == null || nums.length < 3) {
            return lists;
        }
        //对数组元素进行由小到大的排序
        Arrays.sort(nums);
        //定义参考点右侧数组的左右指针,即数组的下标
        int left = 0 , right = 0;
        //设置参考点作为第一个数
        int first = 0;
        int len = nums.length;
        for (int i = 0; i < len && nums[i] < 0; i++) {
            if (left != len - 1) {
                left = i + 1;
            }
            right = len - 1;
            while (true) {
                first = nums[i];
                //否则判断三个数的和是否为零
                int second = nums[left];
                int third = nums[right];
                if (first + second + third == 0) {
                    list.add(first);
                    list.add(second);
                    list.add(third);
                    left++;
                    if (right == left) {
                        break;
                    }
                    //如果三数之和大于0，移动右侧指针
                } else if (first + second + third > 0) {
                    right--;
                    //移动完指针后如果两指针相等，则结束循环
                    if (right == left) {
                        break;
                    }
                    if (nums[right] == nums[right + 1]) {
                        right--;
                        if (right == left) {
                            break;
                        }
                        continue;
                    }
                    //如果三数之和小于0，移动左侧指针
                } else {
                    left++;
                    //移动完指针后如果两指针相等，则结束循环
                    if (right == left) {
                        break;
                    }
                    if (nums[left] == nums[left - 1]) {
                        left++;
                        if (right == left) {
                            break;
                        }
                        continue;
                    }
                }
                if (!list.isEmpty()) {
                    lists.add(list);
                    list.clear();
                }
            }
        }
        return lists;
    }

LeetCode15. 三数之和

原文：https://www.cnblogs.com/mx-info/p/14754232.html