侧边栏壁纸
  • 累计撰写 416 篇文章
  • 累计创建 65 个标签
  • 累计收到 145 条评论

目 录CONTENT

文章目录

LeetCode 第十五题 三数之和

Z同学
2022-10-04 / 0 评论 / 1 点赞 / 388 阅读 / 1,319 字
温馨提示:
本文最后更新于 2022-10-14,若内容或图片失效,请留言反馈。部分素材来自网络,若不小心影响到您的利益,请联系我们删除。

1. 题目

给你一个整数数组 nums ,判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i != j、i != k 且 j != k ,同时还满足 nums[i] + nums[j] + nums[k] == 0

请你返回所有和为 0 且不重复的三元组。

注意:答案中不可以包含重复的三元组。题目要看明白,然后再结合示例,就能弄懂了。

示例 1:
输入:nums = [-1,0,1,2,-1,-4]
输出:[[-1,-1,2],[-1,0,1]]
解释:
nums[0] + nums[1] + nums[2] = (-1) + 0 + 1 = 0 。
nums[1] + nums[2] + nums[4] = 0 + 1 + (-1) = 0 。
nums[0] + nums[3] + nums[4] = (-1) + 2 + (-1) = 0 。
不同的三元组是 [-1,0,1] 和 [-1,-1,2] 。
注意,输出的顺序和三元组的顺序并不重要。


示例 2:
输入:nums = [0,1,1]
输出:[]
解释:唯一可能的三元组和不为 0 。


示例 3:
输入:nums = [0,0,0]
输出:[[0,0,0]]
解释:唯一可能的三元组和为 0 。

提示:

  • 3 <= nums.length <= 3000
  • -105 <= nums[i] <= 105

2. 解题

直接上官方的示例结果: (PS:官方的注释已经写的很多了,就直接用官方的代码了。)

class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
 		int n = nums.length; // 得到数组的长度
        Arrays.sort(nums); // 从小到大针对数组进行排序
        List<List<Integer>> ans = new ArrayList<List<Integer>>(); //创建数据数组
        for (int first = 0; first < n; ++first) {
            // 需要和上一次枚举的数不相同, 除下标为0的数,如果当前值和上一轮的值相同,就跳过本次循环执行下一轮新的循环。
            if (first > 0 && nums[first] == nums[first - 1]) {
                continue;
            }
            //third 对应的指针初始指向数组的最右端 。定义值为C
            int third = n - 1;
            int target = -nums[first]; //当前数值的负数作为目标值,也就是目标target+nums[first]=0; 定义值为A
            // 循环枚举其中的 B值, 满足A+C+B=0;
            // 开始位置为 当前下标的后一位,到数组长度
            for (int second = first + 1; second < n; ++second) {
                // 需要和上一次枚举的数不相同,如果相同就跳过当前循环进入下一轮循环。
                if (second > first + 1 && nums[second] == nums[second - 1]) {
                    continue;
                }
                // 需要保证 b 的指针在 c 的指针的左侧,如果B+C >target 就代表不能满足A+B+C=0;C的坐标就往后缩减。
                while (second < third && nums[second] + nums[third] > target) {
                    --third;
                }
                // 如果指针重合,随着 b 后续的增加
                // 就不会有满足 a+b+c=0 并且 b<c 的 c 了,可以退出循环。A,C值重新再获取
                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]);
                    ans.add(list);
                }
            }
        }
        return ans;
    }
}

执行用时: 21 ms

内存消耗: 45.9 MB

可是速度效率不咋的啊。 优化了之后,速度提高了,内存占用变大了。

class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
       List<List<Integer>> lists = new ArrayList<>();
        int len = nums.length;
        if (len <= 2) {
            return lists;// 直接返回为空
        }
        //排序,将混乱的数组,按照从小到大的顺序进行排序
        Arrays.sort(nums);
        int tmp;
        int L, R,a; //用于标注 左边和右边的下标。
        for (int i = 0; i < len; ++i) { //循环整个数组
            a = nums[i];  // 得到当前的值,该值就是 a+b+c 中的 a
            if (a > 0) return lists; // 如果当前的值为0以上的数,则停止循环。
            if (i > 0 && a == nums[i - 1]) // 如果不是第一个数,并且当前与前一个数相同。那么跳过直到不同为止。 必须比较前一个数,否则会有遗漏。
                continue; //结束本次循环 i++ 进入下一轮循环。
            L = i + 1;// b的数值 从i+1 开始循环
            R = len - 1; // c的值,从len-1开始循环
            
            while (L < R) { // 只要右侧下标 大于左侧下标就循环,如果里面配置不到位容易陷入死循环
                
                tmp = a + nums[L] + nums[R];// 得到当前累加结果
                if (tmp == 0) {  // 满足要求,a+b+c =0
                    List<Integer> list = new ArrayList<>();
                    list.add(a);
                    list.add(nums[L]);
                    list.add(nums[R]);
                    lists.add(list);
                  
                    // 如果当前两个值都相同,那么避免出现重复,需要修改某个值 直到是否有相同的。
                    while (L < R && nums[L + 1] == nums[L])   // 左侧值进行逼近,
                        ++L;
                    while (L < R && nums[R - 1] == nums[R])
                        --R;//右侧值进行循环逼近
                    ++L;
                    --R;
                } else if (tmp < 0) {  // 不满足需求,但如果结果值小于0 ,就移动左侧
                    ++L;
                // } else if (a + nums[L] < nums[i] || a + nums[L] > nums[L]) {
                //     break;
                } else {//其他情况下,就移动右侧值
                    --R;
                }
            }
        }
        return lists;
    }
}

执行用时: 17 ms

内存消耗: 46.1 MB

上面的解法都是,通过排序+双指针进行的。

参考链接:

https://leetcode.cn/problems/3sum

1

评论区