【刷题记录】15. 三数之和

2022 年 7 月 19 日
本文字数：1126 字
阅读完需：约 4 分钟

一、题目描述

给你一个包含 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
-105 <= nums[i] <= 105

二、思路分析

排序后，双指针解法先对数组进行排序，排序后如果存在，负数在左正数在右的分布。

我们定义一个指针 num[i] 遍历这个排序后的数组
为了使三个数之和为 0 那肯定同时存在负数和正数，所以 num[i]确定的情况下，我们再定义两个指针(L,R)从两边开始遍历，使 L + num[i] + R == 0 即为一组三元组，遍历过程中：
若和大于 0，说明 R 太大，R 左移
若和小于 0，说明 L 太小，L 右移
出现重复元素跳过
不满足 L < R 结束
nums[i] > 0 因为已经排序好，所以后面不可能有三个数加和等于 0，直接返回
数组为 null 或者数组长度小于 3, 直接返回

三、代码实现

class Solution {    public static List<List<Integer>> threeSum(int[] nums) {        List<List<Integer>> res = new ArrayList();        int len = nums.length;        if(nums == null || len < 3) return res;
        // 排序        Arrays.sort(nums);
        for (int i = 0; i < len ; i++) {            // 如果当前数字大于0，则三数之和一定大于0，所以结束循环            if(nums[i] > 0) break;            // 去重            if(i > 0 && nums[i] == nums[i-1]) continue;            int L = i + 1;            int R = len - 1;            while(L < R){                int sum = nums[i] + nums[L] + nums[R];                if(sum == 0){                    res.add(Arrays.asList(nums[i],nums[L],nums[R]));                    // 去重                    while (L<R && nums[L] == nums[L+1]) L++;                    while (L<R && nums[R] == nums[R-1]) R--;                    L++;                    R--;                }                else if (sum < 0) L++;                else if (sum > 0) R--;            }        }        return res;    }}

复制代码

复杂度分析

时间复杂度： $O (n^{2})$ ，其中 n 是数组 nums 的长度

空间复杂度： $O (1)$ , 指针使用常数大小的额外空间

运行结果

总结

这道题因为和为零必定正负同时存在，所以我们排序后，在确定一个数的情况下，使用双指针追从俩边来进行遍历查找符合条件的数字是最直接快速点的。

这道题也算是个双指针运用的变形题目吧。

发布于: 刚刚阅读数: 3

原文链接:【http://xie.infoq.cn/article/529bb2e760e57414b7726f0c9】。

WangNing

关注

还未添加个人签名 2020.10.13 加入

一个只想提(快)升(乐)自(摸)我(鱼)的混子选手～

发布

暂无评论

创作场景

【刷题记录】15. 三数之和

一、题目描述

二、思路分析

三、代码实现

复杂度分析

运行结果

总结

WangNing

评论