当前位置: 首页 > 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_…...

golang循环变量捕获问题​​

在 Go 语言中&#xff0c;当在循环中启动协程&#xff08;goroutine&#xff09;时&#xff0c;如果在协程闭包中直接引用循环变量&#xff0c;可能会遇到一个常见的陷阱 - ​​循环变量捕获问题​​。让我详细解释一下&#xff1a; 问题背景 看这个代码片段&#xff1a; fo…...

质量体系的重要

质量体系是为确保产品、服务或过程质量满足规定要求&#xff0c;由相互关联的要素构成的有机整体。其核心内容可归纳为以下五个方面&#xff1a; &#x1f3db;️ 一、组织架构与职责 质量体系明确组织内各部门、岗位的职责与权限&#xff0c;形成层级清晰的管理网络&#xf…...

MODBUS TCP转CANopen 技术赋能高效协同作业

在现代工业自动化领域&#xff0c;MODBUS TCP和CANopen两种通讯协议因其稳定性和高效性被广泛应用于各种设备和系统中。而随着科技的不断进步&#xff0c;这两种通讯协议也正在被逐步融合&#xff0c;形成了一种新型的通讯方式——开疆智能MODBUS TCP转CANopen网关KJ-TCPC-CANP…...

全面解析各类VPN技术:GRE、IPsec、L2TP、SSL与MPLS VPN对比

目录 引言 VPN技术概述 GRE VPN 3.1 GRE封装结构 3.2 GRE的应用场景 GRE over IPsec 4.1 GRE over IPsec封装结构 4.2 为什么使用GRE over IPsec&#xff1f; IPsec VPN 5.1 IPsec传输模式&#xff08;Transport Mode&#xff09; 5.2 IPsec隧道模式&#xff08;Tunne…...

VM虚拟机网络配置(ubuntu24桥接模式):配置静态IP

编辑-虚拟网络编辑器-更改设置 选择桥接模式&#xff0c;然后找到相应的网卡&#xff08;可以查看自己本机的网络连接&#xff09; windows连接的网络点击查看属性 编辑虚拟机设置更改网络配置&#xff0c;选择刚才配置的桥接模式 静态ip设置&#xff1a; 我用的ubuntu24桌…...

MFE(微前端) Module Federation:Webpack.config.js文件中每个属性的含义解释

以Module Federation 插件详为例&#xff0c;Webpack.config.js它可能的配置和含义如下&#xff1a; 前言 Module Federation 的Webpack.config.js核心配置包括&#xff1a; name filename&#xff08;定义应用标识&#xff09; remotes&#xff08;引用远程模块&#xff0…...

Elastic 获得 AWS 教育 ISV 合作伙伴资质,进一步增强教育解决方案产品组合

作者&#xff1a;来自 Elastic Udayasimha Theepireddy (Uday), Brian Bergholm, Marianna Jonsdottir 通过搜索 AI 和云创新推动教育领域的数字化转型。 我们非常高兴地宣布&#xff0c;Elastic 已获得 AWS 教育 ISV 合作伙伴资质。这一重要认证表明&#xff0c;Elastic 作为 …...

spring Security对RBAC及其ABAC的支持使用

RBAC (基于角色的访问控制) RBAC (Role-Based Access Control) 是 Spring Security 中最常用的权限模型&#xff0c;它将权限分配给角色&#xff0c;再将角色分配给用户。 RBAC 核心实现 1. 数据库设计 users roles permissions ------- ------…...

算法打卡第18天

从中序与后序遍历序列构造二叉树 (力扣106题) 给定两个整数数组 inorder 和 postorder &#xff0c;其中 inorder 是二叉树的中序遍历&#xff0c; postorder 是同一棵树的后序遍历&#xff0c;请你构造并返回这颗 二叉树 。 示例 1: 输入&#xff1a;inorder [9,3,15,20,7…...

篇章二 论坛系统——系统设计

目录 2.系统设计 2.1 技术选型 2.2 设计数据库结构 2.2.1 数据库实体 1. 数据库设计 1.1 数据库名: forum db 1.2 表的设计 1.3 编写SQL 2.系统设计 2.1 技术选型 2.2 设计数据库结构 2.2.1 数据库实体 通过需求分析获得概念类并结合业务实现过程中的技术需要&#x…...