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

[C国演义] 第十三章

第十三章

  • 三数之和
  • 四数之和

三数之和

力扣链接

根据题目要求:

  1. 返回的数对应的下标各不相同
  2. 三个数之和等于0
  3. 不可包含重复的三元组 – – 即顺序是不做要求的
    如: [-1 0 1] 和 [0, 1, -1] 是同一个三元组
  4. 输出答案顺序不做要求

暴力解法: 排序 + 3个for循环 + 去重 — — N^3, 肯定超时
优化: 排序 + 双指针 + 去重 — — N^2
优化的具体思路:
固定一个数, 记作a; 在剩余的空间里面找和为 -a的两个数(由于是排好序的, 所以使用双指针)
去重有两种方法:
1.set去重
2 在循环内部缩小空间 — — 非常值得我们去尝试

  1. set去重
class Solution {
public:vector<vector<int>> threeSum(vector<int>& nums) {// 排序sort(nums.begin(), nums.end());// 记录结果vector<vector<int>> res; // 固定一个数 + 双指针int n = nums.size();for(int i = 0; i < n; i++) // 固定一个数{// 双指针优化int left = i+1, right = n-1;int targt = -nums[i];while(left < right){int sum = nums[left] + nums[right];if(sum < targt){left++;}else if(sum > targt){right--;}else{res.push_back({nums[i], nums[left], nums[right]});left++;right--;}}}// 去重set<vector<int>> result(res.begin(), res.end());res.clear();for(auto e : result){res.push_back(e);}return res;}
};


上面的运行结果太慢了, 我们尝试一下 缩小空间去重👇👇👇

  1. 缩小空间去重
class Solution {
public:vector<vector<int>> threeSum(vector<int>& nums) {// 排序sort(nums.begin(), nums.end());// 记录结果vector<vector<int>> res; // 固定一个数 + 双指针int n = nums.size();for(int i = 0; i < n;) // 固定一个数{// 双指针优化int left = i+1, right = n-1;int targt = -nums[i];while(left < right){int sum = nums[left] + nums[right];if(sum < targt){left++;}else if(sum > targt){right--;}else{res.push_back({nums[i], nums[left], nums[right]});left++;right--;// 去重left 和 rightwhile(left < right && nums[left] == nums[left-1])  left++;while(right > left && nums[right] == nums[right+1])  right--;}}// 去重ii++;while(i < n && nums[i] == nums[i-1])  i++;}return res;}
};



四数之和

力扣链接

这一题就跟上面的题目相似, 思路也很相似: 排序 + 固定两个数, 双指针优化 + 去重. 当然, 我们这里的去重逻辑也是 缩小空间去重

class Solution {
public:vector<vector<int>> fourSum(vector<int>& nums, int target) {sort(nums.begin(), nums.end());vector<vector<int>> res;int n = nums.size();// 选定一个数, 内部用三数之和for(int i = 0; i < n;){// 选定一个数, 内部使用双指针优化for(int j = i+1; j < n;){int left = j+1, right = n-1;long int tar = target - (long int)(nums[i]+nums[j]);while(left < right){long int cur = nums[left] + nums[right];if(cur < tar)  left++;else if(cur > tar)  right--;else{res.push_back({nums[i], nums[j], nums[left], nums[right]});left++, right--;// 去重left 和 rightwhile(left < right && nums[left] == nums[left-1])  left++;while(right > left && nums[right] == nums[right+1])  right--;}}// j的去重j++;while(j < n && nums[j] == nums[j-1])  j++;}// i的去重i++;while(i < n && nums[i] == nums[i-1])  i++;}return res;}
};


号令风霆迅,天声动北陬。
长驱渡河洛,直捣向燕幽。
马蹀阏氏血,旗袅可汗头。
归来报明主,恢复旧神州。 — — [宋] 岳飞 <送紫岩张先生北伐>

相关文章:

[C国演义] 第十三章

第十三章 三数之和四数之和 三数之和 力扣链接 根据题目要求: 返回的数对应的下标各不相同三个数之和等于0不可包含重复的三元组 – – 即顺序是不做要求的 如: [-1 0 1] 和 [0, 1, -1] 是同一个三元组输出答案顺序不做要求 暴力解法: 排序 3个for循环 去重 — — N^3, …...

<二>Qt斗地主游戏开发:过场动画的实现

1. 过场动画效果 2. 思路分析 过场动画较为简单&#xff0c;只有一个进度条在进行滚动&#xff0c;因此实现起来不需要动画相关处理&#xff0c;仅需要图片和定时器设定&#xff0c;让进度条动起来即可。我们可以创建一个对话框&#xff0c;设定背景图片以及对话框透明无边框&a…...

链式法则(Chain Rule)

定义 链式法则&#xff08;Chain Rule&#xff09;是概率论和统计学中的一个基本原理&#xff0c;用于计算联合概率分布或条件概率分布的乘积。它可以用于分解一个复杂的概率分布为多个较简单的条件概率分布的乘积&#xff0c;从而简化概率分析问题。 链式法则有两种常见的形…...

AUTOSAR COM模块框架梳理

框架&#xff1a; COM的功能主要就是两个&#xff1a; 把IPDU内的signal提取出来提供给SWC使用&#xff0c;把SWC发送的signal拷贝到IPDU buffer内 所以&#xff0c;COM的关键字是 signal, signal group, IPDU, IPDU group Signal group 是为了保证 Complex Data Types 的数…...

详细介绍区块链之挖矿

对不起&#xff0c;大家&#xff0c;这篇文章对作者来说实在是太有意义和含金量了&#xff0c;作者想把它设置为关注博主才能见全文&#xff0c;请大家理解&#xff01;如果觉得还是看不懂&#xff0c;抱歉耽误大家的时间&#xff0c;就请取消关注&#xff01;&#xff01;&…...

华为OD机试真题-路灯照明问题(Java/C++/Go/Python)

【华为OD机试真题】路灯照明问题(Java/C++/Go/Python) 题目描述 在一条笔直的公路上安装了N个路灯,从位置0开始安装,路灯之间间距固定为100米。 每个路灯都有自己的照明半径,请计算第一个路灯和最后一个路灯之间,无法照明的区间的长度和。 输入描述 第一行为一个数N…...

嵌入式技术面试基本规则

潜规则1&#xff1a;面试的本质不是考试&#xff0c;而是告诉面试官你会做什么 经验不够的小伙伴特别容易犯的一个错误&#xff0c;不清楚面试官到底想问什么&#xff0c;其实整个面试中面试官并没有想难倒你的意思&#xff0c;只是想通过提问的方式来知道你会什么。 比如stm…...

osg实现自定义插件读取自定义格式的模型文件到场景

目录 1. 前言 2. 预备知识 3. 工具、原料 4. 代码实现 1. 前言 osg提供了很多插件来读取模型文件到场景中&#xff0c;这些插件支持大约70种格式类型的文件&#xff0c;但现实中的文件是各式各样&#xff0c;osg不可能囊括所有类型文件&#xff0c;当osg不支持某种类型格式…...

redis进阶

redis.conf 启动的时候就通过配置文件来启动的&#xff01; # 这个不是配置的&#xff0c;就是在这儿说明一下 # 当配置中需要配置内存大小时&#xff0c;可以使用 1k, 5GB, 4M 等类似的格式&#xff0c;其转换方式如下(不区分大小写) # # 1k > 1000 bytes # 1kb > 102…...

(一)正点原子STM32MP135移植——准备

一、简述 使用板卡&#xff1a;正点原子的ATK-DLMP135 V1.2 从i.mx6ull学习完过来&#xff0c;想继续学习一下移植uboot和内核的&#xff0c;但是原子官方没有MP135的移植教程&#xff0c;STM32MP157的移植教程用的又是老版本的代码&#xff0c;ST官方更新后的代码不兼容老版本…...

Kotlin的关键字 lateinit 和 lazy

序、完善一下曾经的草稿。 Kotlin通常要求我们在定义属性后立即对起进行初始化&#xff0c;当我们不知道理想的初始值时&#xff0c;这样做似乎很奇怪&#xff0c;尤其是在生命周期驱动android属性的情况下。 lateinit 简介 lateinit&#xff0c;Kotlin提供的一个可以延迟初…...

阿里云服务器ECS详细介绍_云主机_服务器托管_弹性计算

阿里云服务器ECS英文全程Elastic Compute Service&#xff0c;云服务器ECS是一种安全可靠、弹性可伸缩的云计算服务&#xff0c;阿里云提供多种云服务器ECS实例规格&#xff0c;如经济型e实例、通用算力型u1、ECS计算型c7、通用型g7、GPU实例等&#xff0c;阿里云服务器网分享阿…...

12、建立健全人员培训体系

9、大小屏分离与精细化审核 10、质量审核的设立与合并 11、视频分类建议 内容仓为公司其他部门输送了许多人才&#xff0c;既包括有潜力的主管&#xff0c;也有表现突出或者具备某些特殊能力的员工&#xff0c;从内容仓走出的同事&#xff0c;有些已经成为公司重要业务某个方…...

代码随想录算法训练营第五十九天 | 647. 回文子串 516.最长回文子序列

1. 回文子串 647. 回文子串 - 力扣&#xff08;LeetCode&#xff09; 一个子串左右两个元素相等&#xff0c;并且中间对称&#xff0c;才是回文子串 即 ij 时&#xff0c;[i1: j-1]对称 dp[i][j]&#xff1a; [i:j] 是否是回文字串 当 子串长度大于2 由 dp[i1][j-1] 推出…...

React Redux

redux是什么 Redux是一个模式和库&#xff0c;用于管理和更新应用程序状态&#xff0c;使用称为“action”的事件。它是需要在整个应用程序中使用的状态的集中存储&#xff0c;规则确保状态只能以可预测的方式更新。 Redux主要有三个功能&#xff1a; 获取当前状态更新状态监…...

StreamingLLM - 处理无限长度的输入

文章目录 关于 StreamingLLM使用关于 StreamingLLM Efficient Streaming Language Models with Attention Sinks GitHub : https://github.com/mit-han-lab/streaming-llm论文:https://arxiv.org/abs/2309.17453在流媒体应用程序(如多轮对话)中 部署大型语言模型(LLM)是迫…...

[Linux 命令] nm 详解

1. nm 命令&#xff1a; 显示关于指定 File 中符号的信息&#xff0c;文件可以是对象文件、可执行文件或对象文件库。如果文件没有包含符号信息&#xff0c;nm 命令报告该情况&#xff0c;但不把它解释为出错条件。 nm 命令缺省情况下报告十进制符号表示法下的数字值。 2. 命…...

好文学作品的鉴赏标准

好文学作品的鉴赏标准 2023年诺贝尔文学奖颁给了挪威剧作家约恩福瑟。由于之前的博彩公司给中国作家残雪开出了最高的赔率&#xff0c;以及诺贝尔官方推特在揭晓奖项前发布了一张泰戈尔99年前访华的老照片&#xff0c;残雪的获奖氛围在国内各类媒体的渲染下被拉至极高。当奖项…...

智慧公厕:将科技融入日常生活的创新之举

智慧公厕是当今社会中一项备受关注的创新项目。通过将科技融入公厕设计和管理中&#xff0c;这些公厕不仅能够提供更便利、更卫生的使用体验&#xff0c;还能够极大地提升城市形象和居民生活质量。本文将以智慧公厕领先厂家广州中期科技有限公司&#xff0c;大量的精品案例项目…...

ROS(0)命令及学习资源汇总

ROS安装命令 参考&#xff1a;Ubuntu20.04.4安装ROS Noetic详细教程 - 知乎 安装C和Python3 sudo apt-get install g sudo apt-get install python3 ROS运行小海龟仿真器 roscore确定ROS是否运行成功rosrun turtlesim turtlesim_node运行小海龟仿真器rosrun turtlesim turtle_…...

芯片入门必看:CPU、MCU、SoC、GPU、TPU、NPU

本文首先介绍了芯片的基础分类&#xff0c;包括模拟/数字芯片和逻辑/计算芯片。接着&#xff0c;对8类核心芯片进行了通俗解析&#xff0c;包括CPU、MCU、SoC、GPU、TPU、NPU、FPGA和DSP&#xff0c;涵盖了它们的定义、用途、类型和代表性标的。最后&#xff0c;文章从通用性和…...

先进制程重塑晶圆代工格局:从HPC需求到供应链博弈

1. 行业现状&#xff1a;先进制程如何重塑晶圆代工格局最近和几位在芯片设计公司负责流片的朋友聊天&#xff0c;大家讨论最激烈的&#xff0c;除了产能紧张&#xff0c;就是到底要不要、以及何时上更先进的工艺节点。一个普遍的共识是&#xff1a;7纳米和5纳米这类所谓“先进制…...

从CuteCom到代码:手把手教你用I.MX6ULL实现串口双向通信(附完整工程源码)

从CuteCom到代码&#xff1a;手把手教你用I.MX6ULL实现串口双向通信&#xff08;附完整工程源码&#xff09; 在嵌入式开发中&#xff0c;串口通信是最基础也最常用的调试手段之一。无论是简单的数据收发&#xff0c;还是复杂的协议交互&#xff0c;串口都能提供稳定可靠的通信…...

资本可以复制流量,却复制不了《凰标》的天命@凤凰标志

——《凰标》为何无法被批量复刻&#xff1f;一、资本逻辑&#xff1a;无限复制与批量复刻可复制元素资本操作手法结果爆款剧情换皮翻拍同质化内容泛滥流量模式买量算法短期数据狂欢国风外壳元素拼贴文化“快餐”营销套路热搜话题转瞬即逝的热度 资本的核心能力&#xff0c;是复…...

2026年搜索引擎大变革:生成式优化服务如何引领未来趋势

随着AI技术的不断进步&#xff0c;搜索引擎领域正在经历一场前所未有的变革。2026年&#xff0c;我们见证了从传统SEO到生成式引擎优化&#xff08;GEO&#xff09;的重大转变。这场变革不仅改变了用户获取信息的方式&#xff0c;也为企业带来了全新的营销机遇。本文将深入探讨…...

三维扫描平民化实战:从手机APP到高精度重建全流程指南

1. 项目概述&#xff1a;当三维扫描走下神坛几年前&#xff0c;如果你想获取一个真实物体的三维数字模型&#xff0c;那通常意味着你需要联系一家专业的三维扫描服务公司&#xff0c;支付一笔不菲的费用&#xff0c;然后等待专业人士用一台价格堪比一辆豪华轿车的设备&#xff…...

Cursor Pro激活器:终极解决方案告别API限制,实现无限免费使用

Cursor Pro激活器&#xff1a;终极解决方案告别API限制&#xff0c;实现无限免费使用 【免费下载链接】cursor-free-vip [Support 0.45]&#xff08;Multi Language 多语言&#xff09;自动注册 Cursor Ai &#xff0c;自动重置机器ID &#xff0c; 免费升级使用Pro 功能: Youv…...

别再死记硬背了!用MIDI键盘和DAW软件(如FL Studio/Cubase)5分钟搞懂钢琴音区划分

别再死记硬背了&#xff01;用MIDI键盘和DAW软件5分钟搞懂钢琴音区划分 第一次打开DAW的钢琴卷帘窗时&#xff0c;那些密密麻麻的C3、C4编号是否让你一头雾水&#xff1f;作为从乐队吉他手转型音乐制作的过来人&#xff0c;我完全理解这种困惑。传统教材里"小字组"&q…...

数据分析进阶——【连载 5/9】《Power BI数据分析与可视化案例教程》项目5 数据建模

Power BI 数据建模教程&#xff5c;推介总结 适应人群&#xff1a;数据分析师、业务分析人员、财务 / 运营 / 销售岗、高校学生、企业内训学员、Power BI 进阶学习者。 重要性总结&#xff1a;本文档是 Power BI 数据建模核心实操教程&#xff0c;系统讲解数据建模全流程&#…...

[具身智能-653]:人的大脑神经网络就是天然的模拟电路,还是数字电路?

结论先给&#xff1a;人脑神经网络&#xff0c;本质是【天然模拟电路】&#xff0c;不是数字电路这和前面聊的模拟电路频域特性、硬件隐式频域滤波完全同逻辑。一、先分清&#xff1a;数字电路 vs 模拟电路 核心区别数字电路只有0、1两种离散电平&#xff0c;跳变是阶跃式&…...