题目链接:15. 三数之和 - 力扣(LeetCode)

1.常规解法(会超时)

由于这道题需要排除相同的三元组,则可以先将目标数组从小到大排序,再遍历数组找到每个符合条件的三元组,若结果中不包含该三元组,就将该结果添加到目标结果中,代码如下:

    public List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> ret = new ArrayList<>();
        Arrays.sort(nums);
        int n = nums.length;
        for (int i = 0; i < n - 2; i++) {
            for (int j = i + 1; j < n - 1; j++) {
                for (int k = j + 1; k < n; k++) {
                    if (nums[i] + nums[j] + nums[k] == 0) {
                        List<Integer> list = new ArrayList<>();
                        list.add(nums[i]);
                        list.add(nums[j]);
                        list.add(nums[k]);
                        if (!ret.contains(list)) {
                            ret.add(list);
                        }
                    }
                }
            }
        }
        return ret;
    }

2. 双指针算法

和常规解法一样,我们要先将目标数组从小到大排序,由于要求三数之和等于0,我们可以先固定一个数,只需找到剩下的哪两个数与这个数的和为0,再定义一个顺序表存放三元组。

定义三个指针left,right,p,先将p固定在最后一个数,left在第一个数的位置,right在倒数第二个数的位置,接下来在每一轮循环中,保持p不动,只要移动left和right即可。

当nums[left] + nums[right] + nums[p] > 0,由单调性知,若保持right不动,left右边的数均大于left指向的数,导致三数之和只会越加越大(数组是从大到小排序的),这时就要将right向左移动一位;当nums[left] + nums[right] + nums[p] < 0,由单调性知,若保持left不动,right左边的数均小于right指向的数,导致三个数之和会越加越小,这是就要将left向右移动一位;当nums[left] + nums[right] + nums[p] == 0,就要将这个结果添加到顺序表中,由于最后的结果不允许出现相同的三元组,这时就要去重。

去重:若使用contains判断三元组是否重复,代码就会超时,这时我们就要在nums[left] + nums[right] + nums[p] == 0时,将与left和right指向的数的相同的数去掉,由于这个数组是有序的,那么相同的数就会聚集在一起,只需要使用while循环去重即可;相同的,当left与right相遇时,第一轮循环结束,也去要进行去重操作,将与p指向的数相同的数跳过即可。

优化:当p指向的元素小于0时,由单调性知,p左边的元素均小于0,就不存在三个数之和为0的情况,直接返回结果即可。

流程图与代码如下:

    public List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> ret = new ArrayList<>();
        Arrays.sort(nums);
        int n = nums.length;
        int p = n - 1;
        while (p > 1) {
            int left = 0;
            int right = p - 1;
            if (nums[p] < 0) {
                return ret;
            }
            while (left < right) {
                if (nums[left] + nums[right] + nums[p] < 0) {
                    left++;
                } else if (nums[left] + nums[right] + nums[p] > 0) {
                    right--;
                } else {
                    List<Integer> list = new ArrayList<>();
                    list.add(nums[left]);
                    list.add(nums[right]);
                    list.add(nums[p]);
                    ret.add(list);
                    int numLeft = nums[left++];
                    while (nums[left] == numLeft && left < right) {
                        left++;
                    }
                    int numRight = nums[right--];
                    while (nums[right] == numRight && left < right) {
                        right--;
                    }
                }
            }
            int numP = nums[p--];
            while (nums[p] == numP && p > 1) {
                p--;
            }
        }
        return ret;
    }

 希望大家积极指出不足之处

点赞(0) 打赏

评论列表 共有 0 条评论

暂无评论

微信公众账号

微信扫一扫加关注

发表
评论
返回
顶部