LeetCode 15. 三数之和

server/2025/1/15 7:14:44/

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

1. 理解题意

题意:给一个数组 nums,找出一个三元组,且这三个数字的下标两两互不相同,并且这三个数字相加之和为0,返回能够满足条件的且不重复的三元组。

这里的不重复,可以说是这道题最麻烦的一点,什么叫重复,比如: [0,-1,1] 和 [-1,0,1] 就是重复的。

2. 解决问题的思路

做这种问题,我们首先大概率想到的就是暴力枚举,因为它无脑,简单。

2.1. 暴力枚举

枚举出所有的三元组,接下来的操作就是去重,去重,也很简单,我们可以通过 set 去重,写一段伪代码,进攻参考:

for (size_t i = 0; i < n; ++i)
{for (size_t j = i + 1; j < n; ++j){for (size_t k = j + 1; k < n; ++k){if (IsVaild(nums[i], nums[j], nums[k]))myset.insert({ nums[i], nums[j], nums[k] });}}
}

上面枚举的时间复杂度为 O(N^3), 如果提交,是会超时的。

2.2. 双指针 + 单调性

要使用双指针 + 单调性解决问题,首先需要数据有序,这是前提。

三数之和,我们其实可以看成一个二树之和,为什么呢?

比如 a + b + c == 0, 这是一个三数之和;我们也可以看成  (a + b) == -c,而这就是一个两数之和,两数之和,我们解决过。

因此,三数之和这个问题,我们可以按照如下思路解决:
在有序数组中,先固定一个值,这个值就是上面的 c;

然后,在剩下的区间中,采用两数之和的方案 (双指针 + 单调性),找到 a + b == -c 的情况,此时的 a、b、c 就是一个满足题目要求的三元组。

接下来就是去重的操作了。

关于去重,如果在刷题,可以采用 set 去重,但如果是面试,建议不要用set,我们想想,什么情况会出现重复的三元组呢?

我们通过实例来理解,比如 nums = [-2,0,0,0,1,1,2,2],如下:

此时 c  = -2, a = 0, b = 2, a + b + c 正好等于 0,因此,这就是一个合适的三元组,接下来,a 向右移动,b向左移动,因为此时 c 是固定的,a 向右移还是0,如果此时能构成合适的三元组,那么 b 一定是 2,换言之,此时 a = 0 就没有在判断的必要了,即 a = 0 能不能构成三元组都没有意义,因为就算能构成,也是重复的,故,此时 a 应该跳过0,同理, b 应该跳过 2,如下所示:

上面就是去重的逻辑,可是针对这一道题光有去重不够,我们还需要不漏,不漏指的是,在找到一个合适的三元组后,继续判断,直到 a 和 b 相遇,相遇后, c 向右移动,重复上述过程。

2.3. 代码编写 

理解了上面,代码如下:

class Solution {
public:inline int Compare(int x, int y, int target){return x + y - target;}vector<vector<int>> threeSum(vector<int>& nums) {// 排序std::sort(nums.begin(), nums.end());std::vector<std::vector<int>> ret;// 固定值, 相当于上图中的 c 的下标int objpos = 0;while(objpos <= nums.size() - 3){// 最小值都大于0了, 后序就没必要在判断了, 一定没有合适的三元组if(nums[objpos] > 0)  break;int target = nums[objpos] * -1;// left 相当于 a 的下标int left = objpos + 1;// right 相当于 b 的下标int right = nums.size() - 1;// 这个逻辑就是两数之和的逻辑while(left < right){int mid_ret = Compare(nums[left], nums[right], target);if(mid_ret > 0) right--;else if(mid_ret < 0) left++;else{ret.push_back({nums[objpos], nums[left], nums[right]});// 不漏++left;--right;// 去重while(left < right && nums[left] == nums[left - 1])++left;while(left < right && nums[right] == nums[right + 1])--right;}}++objpos;// 去重while(objpos <= nums.size() - 3 && nums[objpos] == nums[objpos - 1])++objpos;}return ret;}
};


http://www.ppmy.cn/server/28256.html

相关文章

【计算机网络】网络层总结

目录 知识梗概 IP地址 子网划分 IP包头格式 路由 网络层协议 ARP病毒/ARP欺骗 知识梗概 IP地址 IP相关介绍&#xff1a;机器之间需要交流&#xff0c;必须要一个地址才能找到对应的主机&#xff0c;IP地址是主机的一种表示&#xff0c;保证主机之间的正常通信&#xff…

alsactl 保存音频配置

在root下执行 1、关闭音频通道 amixer cset numid2,ifaceMIXER,namePlayback Path OFF2、保存关闭的音频通道 alsactl store -f /var/lib/alsa/asound.state3、恢复保存关闭的音频配置 alsactl restore -f /var/lib/alsa/asound.state4、打开音频通道 amixer cset numid2,ifac…

Java中的IO流

IO流的概述和分类 IO流分为输入输出流 输入流&#xff1a;读数据 输出流&#xff1a;写数据 流&#xff1a;是一种抽象的概念&#xff0c;是对数据传输的总称&#xff0c;流的本质是数据传输 按照数据类型来分 字节流&#xff1a;字节输入流&#xff0c;字节输出流 字符…

“魔数“是怎样工作的?

"魔数"是怎样工作的? 我们经常需要检查某个文件/某块磁盘是否符合我们需要的格式。一般会按照这个文件的完整格式&#xff0c;进行一次全面的分析。 在一个较早的版本&#xff0c;UNIX的可执行文件格式最开头包含一条PDP-11平台上的跳转指令&#xff0c;使得在PDP…

【研发管理】产品经理知识体系-产品创新中的市场调研

导读&#xff1a;在产品创新过程中&#xff0c;市场调研的重要性不言而喻。它不仅是产品创新的起点&#xff0c;也是确保产品成功推向市场的关键步骤。对于产品经理系统学习和掌握产品创新中的市场调研相关知识体系十分重要。 目录 概述&#xff1a;市场调研重要性 1、相关概…

Stable Diffusion教程:额外功能/后期处理/高清化

"额外功能"对应的英文单词是Extras&#xff0c;算是直译。但是部分版本中的翻译是“后期处理”或者“高清化”&#xff0c;这都是意译&#xff0c;因为它的主要功能是放大图片、去噪、修脸等对图片的后期处理。注意这里边对图片的处理不是 Stable Diffusion 本身的能…

java POI解析Excel大文件,获取表头

目录 前言依赖代码StreamingReader的openWorkbookFactory的createCSV解析首行 前言 poi解析大excel文件可能出现oom&#xff0c;同样大小文件&#xff0c;xlsx会oom&#xff0c;xls不会&#xff0c;所以使用流式的方式改造解析xlsx文件的代码。 我的需求是提取每一页的表头&am…

CKEditor编辑器的简单使用方法,取值,赋值

先从官网下载包。CKEditor 4 - Download Latest Version. 一&#xff1a;在项目里引用JQ基础包和CK的JS包 <script src"/JS/jquery-3.4.1.js?v1.0"></script><script src"/ckeditor/ckeditor.js"></script> 二&#xff1a;在表…