leetcode|中等:15. 三数之和

jupiter
2022-03-24 / 0 评论 / 535 阅读 / 正在检测是否收录...
温馨提示:
本文最后更新于2022年03月24日,已超过702天没有更新,若内容或图片失效,请留言反馈。

1.题目

给你一个包含 n 个整数的数组 nums,判断 nums 中是否存在三个元素 a,b,c ,使得 a + b + c = 0 ?请你找出所有和为 0 且不重复的三元组。

注意:答案中不可以包含重复的三元组

示例 1:

输入:nums = [-1,0,1,2,-1,-4]
输出:[[-1,-1,2],[-1,0,1]]

示例 2:

输入:nums = []
输出:[]

示例 3:

输入:nums = [0]
输出:[]

提示:

  • $0 <= nums.length <= 3000$
  • $-10^5 <= nums[i] <= 10^5$

2. 题解

2.1 思路分析

首先对数组进行排序,排序后固定一个数 nums[i]
如果 nums[i]大于 0,则三数之和必然无法等于 0,结束循环
否则使用左右指针指向nums[i]后面的两端,数字分别为 nums[L]和 nums[R]计算三个数的和 sum 判断是否满足等于0
    等于0则添加进结果集
    小于0则L++(L<R)
    大于0则R--(L<R)

关于去重:
    如果 nums[i]== nums[i-1],则说明该数字重复,会导致结果重复,所以应该跳过
    当 sum == 0 时,nums[L] == nums[L+1]则会导致结果重复,应该跳过,L++
    当 sum == 0 时,nums[R] == nums[R-1] 则会导致结果重复,应该跳过,R--

2.2 代码实现

import java.util.*;

public class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        // 数组排序
        Arrays.sort(nums);

        List<List<Integer>> res = new ArrayList<>();
        if(nums.length>=3) {
            for (int i = 0; i < nums.length; i++) {
                if (nums[i] > 0) break;

                if(i > 0 && nums[i] == nums[i-1]) continue; // 去重

                int L = i + 1; // 左指针
                int R = nums.length - 1; // 右指针

                while (L < R) {
                    while (L < R && nums[L] == nums[L + 1]) L++; // 去重
                    while (L < R && nums[R] == nums[R - 1]) R--; // 去重
                    int sum = nums[i] + nums[L] + nums[R];
                    if (sum == 0) {
                        res.add(Arrays.asList(nums[i], nums[L], nums[R]));
                        L++;
                        R--;
                    } else if (sum < 0) {
                        L++;
                    } else {
                        R--;
                    }
                }
            }
        }
        return res;
    }

    public static void main(String[] args) {
        Solution solution = new Solution();
        System.out.println(solution.threeSum(new int[]{-1, 0, 1, 2, -1, -4}));
    }
}

2.3 提交结果

提交结果执行用时内存消耗语言提交时间备注
通过19 ms45.6 MBJava2022/03/24 20:29添加备注

参考资料

  1. https://leetcode-cn.com/problems/3sum/
  2. https://leetcode-cn.com/problems/3sum/solution/hua-jie-suan-fa-15-san-shu-zhi-he-by-guanpengchn/
0

评论 (0)

打卡
取消