当前位置: 首页 > news >正文

专题一_双指针_三数之和

一:题目解析

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

注:懂下面这道题再看三数之和会简单很多:专题一_双指针_查找总价格为目标值的两个商品-CSDN博客

解析:

1:要找不同位置的三元组,也就是不能同一个元素重复使用

2:三元组重复的定义:假设找到了[-1,0,1] 和 [0,1,-1],尽管不是三个位置的值顺序不同,但是只要是三元组的值相同则为重复!

3:输出的三元组的顺序不重要,可以[-1,0,1],也可以变成 [0,1,-1]

二:算法原理

①:暴力

暴力枚举出来符合要求的三元组,我们还需要去重,所以可以选择对每个三元组进行排序,让其组内是升序,再利用unordered_set<vector<int,int,int>>进行去重,但太过于麻烦

所以可以先对数组进行排升序,再暴力,最后符合要求的三元组直接进行unordered_set去重,但仍然不优秀,时间复杂度高达N^3 (找三元组的三重循环就为N^3)

②:优秀

根据上一题:专题一_双指针_查找总价格为目标值的两个商品-CSDN博客的思路,所以此题无非就是固定最左面的数,其值为targe,然后再剩余的区间找和为-targe的两个值,三元组的和为0!

所以思路:

1:仍然是对初始数组进行排序

2:固定最左面的数,其值为targe

3:该targe往右的区间内,进行双指针找到两个数的和为-targe即可

例子:[-4,-4,-1,0,0,0 1,1,4,4,5,6] ,固定targe为最左的-4,然后在右面的区间找和为4的两个数

4:去重

去重,按照暴力解法采取unordered_set可以,但是不优秀,哈希的开辟和插入都需要耗费时间复杂度,所以我们不用容器,我们可以自己进行去重,虽然理解更难,但是算法更优秀

对双指针的去重:

比如:[-4,-4,-1,0,0,0 1,1,4,4,5,6]中,此时当我们进行到了left为第一个0,right为最后一个4的时候 此时我们找到了和为-4的两个值,然后组成三元组[-4,0,4],然后此时肯定是要left++,right--的,但是呢!left后面的值和组成三元组的0是重复的,right前面的值和组成三元组的4是重复的,所以我们可以直接left移动到1,right也移动到1,再做下次的判断,如图:

但是left如果后面的值都是0,则有可能在去重的时候越界了,right同理!所以我们还要加一步判断,就是在left<right的前提才进行去重! 

对targe的去重:

当targe身为第一个-4的情况遍历完了之后,targe也没有必要再移动到下一个-4了,而是移动到下一个不是-4的位置,同样的,如果全是-4,则targe在去重过程中也会越界,应该加一个targe的小标<n(元素个数)的判断!

一个小优化:

当targe值>0的时候,此时没有必要进行双指针查找三元组的必要了,因为数组本来一开始就是升序,你targe值>0了,再加上后面的两个值,肯定不可能为0!! 

三:代码编写

class Solution {
public:vector<vector<int>> threeSum(vector<int>& nums) {vector<vector<int>> v;//返回值int n = nums.size();//n的定义 sort(nums.begin(), nums.end());//对数组先进行排序 形成升序for (int i = 0; i < n;) {//targe值的固定(从左到右)if (nums[i] > 0) break;//一个小优化 int left = i + 1, right = n - 1, targe = nums[i];//根据i下标 确认left的位置 right初始为最右 targe为固定位置的值while (left < right) {//两指针相遇 代表此次的targe值已经无效 int sum = nums[left] + nums[right];//双指针的和为sumif (sum < -targe) left++;//和小于-targe 代表left应该++else if (sum> -targe) right--;//和大于-targe 代表right应该--else {//代表sum = -targe 找到三元组了v.push_back({nums[i], nums[left], nums[right]});//把这个三元组放进返回值v中left++,right--;//双指针移动while (left < right && nums[left] == nums[left - 1]) //left指针的去重left++;while (left < right && nums[right] == nums[right + 1]) //right指针的去重right--;}}i++;//i移动 也就是targe值的改变while (i < n && nums[i] == nums[i - 1]) i++;//targe值的去重}return v;//返回v}
};

解释:

1:targe为固定的值,所以双指针的和sum和-targe进行比较

2:left right targe的去重,先++(本来就要++),再判断如果相等,就再++,知道和上一次不相等

3:targe的去重,本质就是i的移动,我们在下面已经让targe成为了应该成为的值,所以就去掉了for循环中的i++,否则会出错!如图:

解释:targe为-4的轮次已经过了,应该到-1,但是for循环还有i++,导致跳过-1,来到0了,错误!

四:题目分析

1:和上道题两数之和的区别在于,我们不是找到了一个结果就返回,而是返回全部结果去重后的结果

2:先排序的好处,不仅体现在了时间复杂度,更是方便了我们的去重,因为相同的值都会挨在一起!所以我们才可以手动的去重!

3:时间复杂度为:O(N²)(排序 O(N log N) 可忽略,即使加上也远胜N^3)

http://www.lryc.cn/news/583467.html

相关文章:

  • 【基础算法】贪心 (四) :区间问题
  • WIFI协议全解析04:从芯片角度看WiFi协议:ESP32/8266 支持了哪些?
  • SQL 视图与事务知识点详解及练习题
  • ARM汇编编程(AArch64架构)课程 - 第7章:SIMD与浮点运算
  • STIDGCN(时空交互动态图卷积网络)的原理,包括其核心模块的设计思路和工作机制 交通预测是智能交通系统中的一个重要任务
  • python+vue的企业产品订单管理系统
  • Redis:分组与设备在 Redis 中缓存存储设计
  • Redis-哨兵机制doctor环境搭建
  • CSS基础选择器、文本属性、引入方式及Chorme调试工具
  • Linux 测开:日志分析 + 定位 Bug
  • 【图像处理基石】如何检测到画面中的ppt并对其进行增强?
  • deepseek实战教程-第十篇deepseek对MCP协议支持
  • 计算机网络实验——网线的制作和测试
  • 7、整合前几篇插件列表
  • 云成本优化的核心原则与框架
  • Spring AI 本地 RAG 实战:用Redis、Chroma搭建离线知识问答系统
  • 【解决方法】ollama在powershell或者cmd运行时乱码报错
  • 网络安全之RCE分析与利用详情
  • 从零用java实现 小红书 springboot vue uniapp(13)模仿抖音视频切换
  • uniapp如何创建并使用组件?组件通过Props如何进行数据传递?
  • scp:上传大型数据集到实验室服务器
  • linux-用户和组
  • 家庭网络中的服务器怎么对外提供服务?
  • linux-进程信号的产生与发送
  • Redis分布式锁从入门到放弃:Redisson源码解密
  • 玛哈特网板矫平机:精密矫平金属开平板的利器
  • 掌握 Winget 安装:从 Microsoft Store 到 winget-install 脚本的完整方案
  • 虚幻引擎5 GAS开发俯视角RPG游戏 #5-8:倾听属性变化
  • 基于Matlab多特征融合的可视化指纹识别系统
  • 141-CEEMDAN-VMD-Transformer-BiLSTM-ABKDE多变量区间预测模型!