leetcode15 三数之和
1.哈希法
为了避免重复
class Solution {
public:vector<vector<int>> threeSum(vector<int>& nums) {set<vector<int>> temple;//使用 set 来存储符合条件的三元组,避免重复vector<vector<int>> out;//存放最终输出结果sort(nums.begin(),nums.end());//先进行数组排序for(int i = 0; i < nums.size(); i++){if(i > 0 && nums[i] == nums[i-1]) continue;//如果当前数值与上一轮循环所得数值相同、后续找到的三元组将相同,没必要再找,退出本轮unordered_set<int> hash;//定义哈希表存放待查找内容for(int j = i+1; j < nums.size(); j++){ if(hash.find(-(nums[i] + nums[j])) != hash.end()){temple.insert({nums[i], nums[j], -(nums[i] + nums[j])});//哈希表中存在与当前nums[i]\nums[j]匹配的值 -(nums[i] + nums[j]),即找到了符合条件的三元组将其存入 }hash.insert(nums[j]);//将nums[j]存入,可能成为后续寻找的-(nums[i] + nums[j])值} }for(const auto& t: temple){out.push_back(t);}//遍历三元组将他们存入最终输出的变量中return out;}
};
在解决 三数之和(3Sum)问题时,先对数组进行排序是一个非常重要的步骤。排序不仅简化了问题的解决过程,还能帮助我们高效地处理重复元素和优化查找逻辑。以下是详细解释:
1. 排序的作用
(1)方便去重
排序后,相同的元素会相邻排列。这样,我们可以通过简单的条件判断(如
nums[i] == nums[i - 1]
)来跳过重复的元素,避免重复解。例如,数组
[-1, -1, 0, 1, 2]
中,两个-1
相邻,可以通过判断nums[i] == nums[i - 1]
来跳过第二个-1
。(2)简化查找逻辑
排序后,数组是有序的,可以利用 双指针法 来高效查找满足条件的三元组。
双指针法的时间复杂度是 O(n)O(n),而哈希法的时间复杂度是 O(n2)O(n2),因此排序后使用双指针法可以显著提高性能。
(3)确保结果有序
排序后,找到的三元组
(nums[i], nums[j], nums[k])
也是有序的,这样可以避免重复解(如[-1, 0, 1]
和[0, -1, 1]
被视为不同的解)。
在内层循环中,哈希表的作用是存储已经遍历过的
nums[j]
。每次遍历到一个新的nums[j]
时:
先检查哈希表中是否存在
target = -nums[i] - nums[j]
。
如果存在,说明
nums[i] + nums[j] + target = 0
,即找到一个三元组。然后将当前的
nums[j]
加入哈希表,以便后续的nums[j]
可以使用它来查找目标值。
nums[i]
是外层循环的固定值,它不会被用作目标值(target
),因为target
的定义是-nums[i] - nums[j]
。
去重逻辑
在外层循环中,通过
if (i > 0 && nums[i] == nums[i - 1]) continue;
跳过重复的nums[i]
。在内层循环中,哈希表会自动处理重复的
nums[j]
,因为哈希表的特性是存储唯一的键。
-
const auto& triplet
:-
auto
:自动推导变量类型。在这里,triplet
的类型是const vector<int>&
。 -
const
:表示triplet
是只读的,不能修改。 -
&
:表示引用,避免拷贝vector<int>
,提高效率。
-
2.双指针法
先排序,有一层for循环,定义指针i从下标0的地方开始,同时定一个下标left 定义在i+1的位置上,定义下标right 在数组结尾的位置上。
接下来如何移动left 和right呢, 如果nums[i] + nums[left] + nums[right] > 0 就说明 此时三数之和大了,因为数组是排序后了,所以right下标就应该向左移动,这样才能让三数之和小一些。如果 nums[i] + nums[left] + nums[right] < 0 说明 此时 三数之和小了,left 就向右移动,才能让三数之和大一些,直到left与right相遇为止。
问题分析
-
sum
的计算位置:-
你在外层循环中计算了
sum = nums[i] + nums[left] + nums[right]
,但在内层循环中left
和right
会变化,sum
的值却没有更新,导致逻辑错误。
-
-
去重逻辑:
-
你在找到满足条件的三元组后,没有跳过重复的
nums[left]
和nums[right]
,这可能导致重复解。(多加了
while (left < right && nums[right] == nums[right + 1]) right--;
这一行代码,其实就是把 需要执行的逻辑提前执行了,但并没有减少 判断的逻辑。最直白的思考过程,就是right还是一个数一个数的减下去的,所以在哪里减的都是一样的。
所以这种去重 是可以不加的。 仅仅是 把去重的逻辑提前了而已。
)
-
-
set
的使用:-
你使用
set<vector<int>>
来存储结果,虽然可以避免重复解,但效率较低,因为set
的插入操作是 O(logn)O(logn) 的。
-
-
边界条件:
-
你没有处理数组长度小于 3 的情况。
-
class Solution{
public:vector<vector<int>> threeSum(vector<int>& nums){sort(nums.begin(), nums.end());vector<vector<int>> out;if (nums.size() < 3) {return out;}for(int i = 0; i < nums.size(); i++){if(i > 0 && nums[i] == nums[i - 1]) continue;int left = i + 1, right = nums.size() - 1;while(left<right){int sum = nums[i] + nums[left] + nums[right];if(sum > 0){right --;}if(sum < 0){left ++;}if(sum == 0){out.push_back({nums[i], nums[left], nums[right]});right --;left ++;}} }return out;}
};
相关文章:
leetcode15 三数之和
1.哈希法 为了避免重复 class Solution { public:vector<vector<int>> threeSum(vector<int>& nums) {set<vector<int>> temple;//使用 set 来存储符合条件的三元组,避免重复vector<vector<int>> out;//存放最终输…...
5c/c++内存管理
1. C/C内存分布 int globalVar 1; static int staticGlobalVar 1; void Test() {static int staticVar 1;int localVar 1;int num1[10] { 1, 2, 3, 4 };char char2[] "abcd";const char* pChar3 "abcd";int* ptr1 (int*)malloc(sizeof(int) * 4);i…...
蓝桥备赛(11)- 数据结构、算法与STL
一、数据结构 1.1 什么是数据结构? 在计算机科学中,数据结构是一种 数据组织、管理和存储的格式。它是相互之间存在一种 或多种特定关系的数据元素的集合。 ---> 通俗点,数据结构就是数据的组织形式 , 研究数据是用什么方…...
C++ 二叉搜索树代码
C 二叉搜索树代码 #include <iostream> using namespace std;template<typename T> struct TreeNode{T val;TreeNode *left;TreeNode *right;TreeNode():val(0), left(NULL), right(NULL){}TreeNode(T x):val(x), left(NULL), right(NULL){} };template<typena…...
Flask 打包为exe 文件
进入虚拟环境 激活虚拟环境 .venv\Scripts\activatepython build.py 完成标识图片 已经完成打包了,完成,下边是我自己记录的 这时候,我自己数据库文件夹下是没有sql 脚本的,要自己拷贝下这个路径下的文件 E:\开源文件\python-wi…...
JavaWeb-idea配置smart tomcat
一,安装smart tomcat插件 在插件市场搜索smart tomcat 点击安装,我已经安装成功。 二,web项目配置tomcat 点击这里,选择edit 进来之后,选加号 然后选tomcat 在这里,配置完毕后,点apply&…...
DELETE/ UPDATE/ INSERT 语句会自动加锁
在数据库系统中,DELETE、UPDATE 和 INSERT 语句通常会自动加锁,以确保数据的一致性和并发控制。具体的锁类型和效果取决于数据库的实现(如 MySQL、PostgreSQL 等)以及事务的隔离级别。以下是这些操作通常加锁的行为和效果…...
docker本地部署ollama
启动ollama容器 1.使用该命令启动CPU版运行本地AI模型 docker run -d -v ollama:/root/.ollama -p 11434:11434 --name ollama ollama/ollama 2.此命令用于启动GPU版本运行AI模型 前提是笔记本已配置NVIDIA的GPU驱动,可在shell中输入nvidia-smi查看详细情况…...
Linux线程机制
Linux 操作系统中的线程机制是基于 POSIX 线程(Pthreads) 标准实现的,通常称为 pthread。Linux 内核通过Native POSIX Thread Library提供了对多线程的支持。 1. 线程的基本概念 线程是进程中的一个执行单元,是 CPU 调度的基本单…...
LeetCode热题100JS(44/100)第八天|二叉树的直径|二叉树的层序遍历|将有序数组转换为二叉搜索树|验证二叉树搜索树|二叉搜索树中第K小的元素
543. 二叉树的直径 题目链接:543. 二叉树的直径 难度:简单 刷题状态:1刷 新知识: 解题过程 思考 示例 1: 输入:root [1,2,3,4,5] 输出:3 解释:3 ,取路径 [4,2,1,3] 或…...
Java与数据库
目录 一.本文焦点: 二.数据库常用数据类型 三.对数据库操作 四.对数据库中的表操作 五.条件表达 六. 表查询操作进阶 1.多表连接查询 1)交叉连接查询 2)内连接(取两表交集) 3)外连接 4)…...
MySQL表中数据基本操作
1.表中数据的插入: 1.insert insert [into] table_name [(column [,column]...)] values (value_list) [,(value_list)] ... 创建一张学生表: 1.1单行指定列插入: insert into student (name,qq) values (‘张三’,’1234455’); values左…...
基于GeoTools的GIS专题图自适应边界及高宽等比例生成实践
目录 前言 一、原来的生成方案问题 1、无法自动读取数据的Bounds 2、专题图高宽比例不协调 二、专题图生成优化 1、直接读取矢量数据的Bounds 2、专题图成果抗锯齿 3、专题成果高宽比例自动调节 三、总结 前言 在当今数字化浪潮中,地理信息系统(…...
蓝桥与力扣刷题(蓝桥 数字三角形)
题目: 上图给出了一个数字三角形。从三角形的顶部到底部有很多条不同的路径。对于每条路径,把路径上面的数加起来可以得到一个和,你的任务就是找到最大的和(路径上的每一步只可沿左斜线向下或右斜线向下走)。 输入描述…...
6. PromQL的metric name(在node exporter复制下来交给AI解释的)
目录 前言: Go 运行时指标: Go 内存统计指标: CPU 指标: 内存指标: 磁盘指标: 网络指标: 系统指标: 前言: 写这个得目的是为了后续方便查询,因为在pro…...
Windows设置目录及子目录大小写不敏感暨git克隆报错同名文件已存在的解决办法
在Windows系统中设置目录及其子目录为大小写不敏感,可以通过以下步骤完成: 步骤说明: 以管理员身份运行命令提示符或PowerShell 右键点击“开始”菜单,选择“命令提示符(管理员)”或“Windows PowerShell&…...
关于tresos Studio(EB)的MCAL配置之GPT
概念 GPT,全称General Purpose Timer,就是个通用定时器,取的名字奇怪了点。定时器是一定要的,要么提供给BSW去使用,要么提供给OS去使用。 配置 General GptDeinitApi控制接口Gpt_DeInit是否启用 GptEnableDisable…...
VScode 中文符号出现黄色方框的解决方法
VScode 中文符号出现黄色方框的解决方法 我的vscode的python多行注释中会将中文字符用黄色方框框处: 只需要打开设置搜索unicode,然后将这一项的勾选取消掉就可以了: 取消之后的效果如下: 另一种情况:中文显示出现黄色…...
WordPress使用(3)
前面文章讲述了如何利用docker进行wordpress系统的安装及相关设置,本文将介绍如何进行站点数据和数据库数据的备份。 1. 备份数据库 # 进入mysql容器内部 docker exec -it mysqlwp bash# 使用mysqldump 命令导出数据库 mysqldump -u root -p wordpress > wordp…...
Shell编程概述与Shell变量
目录 一、Shell编程基础 1.1、Shell脚本使用场景 1.2、Shell脚本的格式 1.3、Shell脚本的执行 1.4、Shell脚本错误调试 二、 重定向与管道符 2.1、重定向 2.2、管道符 三、Shell变量 3.1、变量分类 3.2、特殊符号 3.3、整数运算 3.4、read 3.5、局部变量与全局变量…...
使用QT + 文件IO + 鼠标拖拽事件 + 线程 ,实现大文件的传输
第一题、使用qss,通过线程,使进度条自己动起来 mythread.h #ifndef MYTHREAD_H #define MYTHREAD_H#include <QObject> #include <QThread> #include <QDebug>class mythread : public QThread {Q_OBJECT public:mythread(QObject* …...
【电路笔记】-时序逻辑电路
时序逻辑电路 文章目录 时序逻辑电路1、概述2、时序逻辑的分类3、时序逻辑SR触发器4、NAND门SR触发器5、正NAND门SR触发器6、NOR门SR触发器7、时序逻辑作为开关去抖电路8、门控或时钟SR触发器时序逻辑电路使用触发器作为存储元件,其输出取决于输入状态。 1、概述 与组合逻辑电…...
随机树算法 自动驾驶汽车的路径规划 静态障碍物(Matlab)
随着自动驾驶技术的蓬勃发展,安全、高效的路径规划成为核心挑战之一。快速探索随机树(RRT)算法作为一种强大的路径搜索策略,为自动驾驶汽车在复杂环境下绕过静态障碍物规划合理路径提供了有效解决方案。 RRT 算法基于随机采样思想…...
【AI深度学习基础】PyTorch初探
引言 PyTorch 是由 Facebook 开源的深度学习框架,专门针对 GPU 加速的深度神经网络编程,它的核心概念包括张量(Tensor)、计算图和自动求导机制。PyTorch作为Facebook开源的深度学习框架,凭借其动态计算图和直观的API设…...
探索.NET 10 的新特性,开发效率再升级!
前言 最近,.NET 10 发布啦,作为长期支持(LTS)版本,接下来的 3 年里它会给开发者们稳稳的幸福。今天咱就来唠唠它都带来了哪些超实用的新特性。可在指定链接下载。 新特性 下面将介绍了.NET 10的新特性,其…...
< 自用文儿 > CertBot 申请 SSL 证书 使用 challenge 模式 避开防火墙的阻挡
环境: 腾讯 VPS 腾讯会向你销售 SSL , 这个本是免费的。CertBot 默认申请证书要用到 80 端口,会蹭边什么什么条款,备案法律来阻止80端口的通讯,没有网站也一样被阻拦。 通过腾讯买的域名: bestherbs.cn …...
系统架构评估方法-ATAM方法
架构权衡分析方法(Architecture Tradeoff Analysis Method,ATAM) 是在SAAM的基础上 发展起来的,主要针对性能、实用性、安全性和可修改性,在系统开发之前,对这些质量属性 进行评价和折中。 (1)特定目标。 ATAM的目标是在考虑多个相互影响的质…...
deepseek在pycharm 中的配置和简单应用
对于最常用的调试python脚本开发环境pycharm,如何接入deepseek是我们窥探ai代码编写的第一步,熟悉起来总没坏处。 1、官网安装pycharm社区版(免费),如果需要安装专业版,需要另外找破解码。 2、安装Ollama…...
硬通货用Deekseek做一个Vue.js组件开发的教程
安装 Node.js 与 Vue CLI npm install -g vue/cli vue create my-vue-project cd my-vue-project npm run serve 通过 Vue CLI 可快速生成项目骨架,默认配置适合新手快速上手 目录结构 src/ ├── components/ # 存放组件文件 │ └── …...
类、方法和变量可使用的访问控制符和修饰符的表格展示
1. 类的修饰符 修饰符类别修饰符说明访问控制符public顶级类使用时,对所有包可见。嵌套类也可以使用。默认没有写访问修饰符时,仅在同一包内可见。protected (仅嵌套类)同一包内以及不同包的子类可见。private (仅嵌套类)仅在外部类内部可见。非访问修饰…...
FreeRTOS 任务管理与运行时间统计:API 解析与配置实践
1. FreeRTOS 任务相关 API 函数 1.1 FreeRTOS 任务相关 API 函数介绍 FreeRTOS 提供了一系列 API 来管理任务的状态、优先级和运行信息。以下是任务管理相关的主要 API 及其功能说明: 1.1.1 任务优先级管理 API 函数作用uxTaskPriorityGet()获取任务的当前优先级…...
基于提示驱动的潜在领域泛化的医学图像分类方法(Python实现代码和数据分析)
摘要 医学图像分析中的深度学习模型易受数据集伪影偏差、相机差异、成像设备差异等导致的分布偏移影响,导致在真实临床环境中诊断不可靠。领域泛化(Domain Generalization, DG)方法旨在通过多领域训练提升模型在未知领域的性能,但…...
【C++】5.4.3 范围for语句
范围for语句基本形式: for(声明变量:序列容器) {循环执行语句; } 其中,“序列容器”是指花括号括起来的初始值列表、数组、vector或者string等类型的对象,主要特点是拥有能返回迭代器的 begin() 和 end() 成员; “声明变量”是一个类似声明…...
LeetCode 排序章节
快速排序 简单 LCR 159. 库存管理 III 仓库管理员以数组 stock 形式记录商品库存表,其中 stock[i] 表示对应商品库存余量。请返回库存余量最少的 cnt 个商品余量,返回 顺序不限。 示例 1: 输入:stock [2,5,7,4], cnt 1 输出&a…...
常见的限流算法有哪些?
一、固定窗口算法(Fixed Window) 原理: 将时间划分为固定长度的窗口(如1秒、1分钟),每个窗口内统计请求次数,超过阈值则拒绝后续请求。例如:每秒限流100次,窗口结束后计…...
【pyqt】(十一)单选框
控件-单选框 单选框的类名为QRadioBox,在学习新的控件的时候, 需要掌握的内容主要除了属性之外,其信号触发方法也非常重要。还可以利用Designer来辅助我们进行学习,尤其是利用Designer的属性展示和设置。 单选框中,最…...
深度解析:视频软编码与硬编码的优劣对比
视频编码 一、基本原理与核心技术 压缩原理 通过时空冗余消除实现数据压缩: 空间冗余:利用帧内预测(如DC/角度预测)消除单帧内相邻像素相似性。时间冗余:运动估计与补偿技术(ME/MC)减少连续帧间…...
[Windows] 批量为视频或者音频生成字幕 video subtitle master 1.5.2
参考原文:[Windows] 批量为视频或者音频生成字幕 video subtitle master 1.5.2 Video Subtitle Master 1.5.2 介绍 Video Subtitle Master 1.5.2 是一款功能强大的客户端工具,能够批量为视频或音频生成字幕,还支持批量将字幕翻译成其他语言…...
Lab 3 Page Table
题目链接 我的问题: 1 每个进程的kernel stack是干啥的来着?在何时初始化的? 题目2:A kernel page table per process (hard) 1 一些题目要求 Your first job is to modify the kernel so that every process uses its own c…...
爬虫逆向:脱壳工具 frida-dexdump 的使用详解
更多内容请见: 爬虫和逆向教程-专栏介绍和目录 文章目录 1. 工具简介1.1 frida-dexdump介绍1.2 frida-dexdump支持场景1.3 frida-dexdump优点1.4 frida-dexdump工具使用方法2. 环境准备3. 安装 frida-dexdump4. 使用步骤4.1 步骤一:连接 Android 设备4.1 步骤二:安装目标应用…...
图论-腐烂的橘子
994.腐烂的橘子 在给定的 m x n 网格 grid 中,每个单元格可以有以下三个值之一:值 0 代表空单元格; 值 1 代表新鲜橘子; 值 2 代表腐烂的橘子。 每分钟,腐烂的橘子 周围 4 个方向上相邻 的新鲜橘子都会腐烂。返回 直到…...
FPGA-DE2115开发板实现4位全加器、3-8译码器。
文章目录 一、安装quartus二、4位全加器三、3-8译码器(8段数码管)四、参考文章 一、安装quartus 安装quartus参考文章:Quartus Prime 18.0与ModelSim的安装 Quartus II 18.0安装教程(非常详细)从零基础入门到精通&…...
【leetcode hot 100 48】旋转图像
方法一:(原地旋转)对于矩阵中第 i 行的第 j 个元素,在旋转后,它出现在倒数第 i 列的第 j 个位置。matrix[row][col]在旋转后的新位置为matrix[col][n−row−1]。只要旋转四次就能回到原点。 class Solution {public vo…...
TWind 的黑马点评随笔
TWind 的黑马点评随笔 目前是把黑马点评的技术部分完全做完了,不能说吃得饱饱,也算个半饱吧。 黑马点评严格来说不算项目,因为它给的前端过于垃圾,内容又重在Redis,所以称之为Redis练习貌似跟贴切。 尽管如…...
Fork/Join 框架详解:分支合并的高性能并发编程
目录 引言 一、Fork/Join 框架概述 1.1 什么是 Fork/Join 框架? 1.2 Fork/Join 框架的核心组件 二、Fork/Join 框架的使用步骤 三、Fork/Join 框架的示例 3.1 示例 1:计算数组元素之和 代码实现 代码解析 3.2 示例 2:并行排序 代码…...
爬虫逆向:脱壳工具ZjDroid的使用详解
更多内容请见: 爬虫和逆向教程-专栏介绍和目录 文章目录 1. 工具简介2. 环境准备3. ZjDroid工具的使用方法4. 使用步骤4.1 步骤一:连接 Android 设备4.2 步骤二:安装目标应用4.3 步骤三:启动 ZjDroid 脱壳脚本4.4 步骤四:触发应用加载壳内代码4.5 步骤五:获取脱壳后的文件…...
上海市闵行区数据局调研云轴科技ZStack,共探数智化转型新路径
为进一步深化人工智能、大模型技术的应用,推动区域数字经济高质量发展,2025年2月27日,上海市闵行区数据局局长吴畯率队赴上海云轴科技股份有限公司(以下简称“云轴科技ZStack”)开展专题调研。此次调研旨在深入了解企业…...
Python----数据分析(Matplotlib五:pyplot的其他函数,Figure的其他函数, GridSpec)
一、pyplot的其他函数 1.1、xlabel 在matplotlib中, plt.xlabel() 函数用于为当前活动的坐标轴(Axes)设置x轴的 标签。当你想要标识x轴代表的数据或单位时,这个函数非常有用。 plt.xlabel(xlabel text) 1.2、ylabel 在matplotl…...
Android Coil总结
文章目录 Android Coil总结概述添加依赖用法基本用法占位图变形自定义ImageLoader取消加载协程支持缓存清除缓存监听 简单封装 Android Coil总结 概述 Coil 是一个用于 Android 的 Kotlin 图像加载库,旨在简化图像加载和显示的过程。它基于 Kotlin 协程࿰…...
mybatisplus 开发流程
目录 什么是mybatisplus? 创建项目 先创建一个简单的Java项目编辑 引入依赖 1.引入父依赖 2.引入其他依赖 springboot配置 application.yml qppication-dev.yml 创建包 实体类 映射(创建一个接口) 构建测试环境 进行方法的实…...