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

LeetCode 16.最接近的三数之和(C++)

链接

https://leetcode.cn/problems/3sum-closest/description/

题目

给你一个长度为 n 的整数数组 nums 和 一个目标值 target。请你从 nums 中选出三个整数,使它们的和与 target 最接近。

返回这三个数的和。

假定每组输入只存在恰好一个解。

示例1

输入:nums = [-1,2,1,-4], target = 1
输出:2
解释:与 target 最接近的和是 2 (-1 + 2 + 1 = 2) 。

示例2

输入:nums = [0,0,0], target = 1
输出:0

提示

  • 3 <= nums.length <= 1000
  • -1000 <= nums[i] <= 1000
  • -104 <= target <= 104

思路:

先排序,使数据有序,以保证后续可以使用双指针来计算”三数之和“。记录第一次”三数之和“和target的距离(记为sub),并记录此时”三数之和“的值(记为ret)。当"三数之和“大于target时,比较此时"三数之和“和target的距离和sub的大小关系。当此时"三数之和“和target的距离<sub时,更新sub,并更新ret。然后再缩小”三数之和“的值。当”三数之和“小于target时,比较此时"三数之和“和target的距离和sub的大小关系。当此时"三数之和“和target的距离<sub时,更新sub,并更新ret。然后增加”三数之和“的值。当”三数之和“等于target时,意味着重合,距离为0,因此是最小的,更新ret后返回。

代码实现:

class Solution {
public:int threeSumClosest(vector<int>& nums, int target) {sort(nums.begin(),nums.end());int ret , sub;for(int i = 0 ; i < nums.size(); i++)//遍历取得“三数之和“的第一个数{int left = i + 1 , right = nums.size() - 1;if(i == 0) // 记录首次的 sub 和 ret{sub = abs(target - (nums[i] + nums[left] + nums[right]));ret = (nums[i] + nums[left] + nums[right]);}while(left < right){if(nums[i] + nums[left] + nums[right] < target) {if(abs(target - (nums[i] + nums[left] + nums[right])) < sub) // 更新sub和ret{sub = abs(target - (nums[i] + nums[left] + nums[right]));ret = nums[i] + nums[left] + nums[right];}left++;// 增加 nums[left] 的值,从而使得 "三数之和"的值增大}else if (nums[i] + nums[left] + nums[right] == target) //更新ret并返回{ret = nums[i] + nums[left] + nums[right];return ret;}else{if(abs(target - (nums[i] + nums[left] + nums[right])) < sub) // 更新sub和ret{sub = abs(target - (nums[i] + nums[left] + nums[right]));ret = nums[i] + nums[left] + nums[right];}right--;//减小 nums[right]的值,从而使得“三数之和”的值变小}}}return ret;}
};

相关文章:

LeetCode 16.最接近的三数之和(C++)

链接 https://leetcode.cn/problems/3sum-closest/description/ 题目 给你一个长度为 n 的整数数组 nums 和 一个目标值 target。请你从 nums 中选出三个整数&#xff0c;使它们的和与 target 最接近。 返回这三个数的和。 假定每组输入只存在恰好一个解。 示例1 输入&a…...

JSON.parse 解析NaN, Infinity, -Infinity失败

背景 JSON.parse() 方法解析字符串时&#xff0c; 如果字符串包含NaN, Infinity, -Infinity会报错。因为我们需要先将NaN, Infinity, -Infinity替换成字符类型&#xff0c;再做转换 解决方法 function convert(str) {str str.replace(/NaN/g, "NaN");str str.re…...

【计算机】我不允许还有人不知道数据库是什么

数据库是计算机科学中的一个核心概念,它是用于存储、检索、管理和处理数据的系统。在现代的软件开发和信息技术中,数据库扮演着至关重要的角色。以下是关于数据库的一些基本要点: 数据存储: 数据库提供了一个结构化的方式来存储数据,使得数据可以高效地组织和访问。它通过…...

制作WIFI二维码,实现一键扫描连接WIFI

在现代社会&#xff0c;Wi-Fi已成为我们日常生活中不可或缺的一部分。无论是在家庭、办公室还是公共场所&#xff0c;我们都希望能够快速方便地连接到Wi-Fi网络。下面小编就来和大家分享通过制作WIFI二维码&#xff0c;来实现一键扫描就可以连接WIFI的方法。连接WIFI不用在告诉…...

数据结构-图的基本概念

图的定义 图时由非空的顶点集合和一个描述顶点之间关系的集合组成。可以定义为&#xff1a; ​​​​​​​ ​​​​​​​ ​​​​​​​ G表示一个图&#xff0c;V表示点集&#xff0c;E表示边集。集合E的每一个二元组都包含两个值和&#xff0c;表示…...

【HarmonyOS NEXT 】鸿蒙generateBarcode (码图生成)

本模块支持将字符串转换为二维码或条形码&#xff0c;目前已支持的码制式为EAN-8、EAN-13、UPC-A、UPC-E、Codabar、Code 39、Code 93、Code 128、ITF-14、QR Code、Data Matrix、PDF417、Aztec。暂时不支持多功能码生成。 起始版本&#xff1a;4.1.0(11) 导入模块 import {…...

python测试工程师 之 unittest框架总结

unittest 学习目标unittest 框架的基本使⽤⽅法(组成)断⾔的使⽤ (让程序⾃动的判断预期结果和实际结果是否相符)参数化(多个测试数据, 测试代码写⼀份 传参)⽣成测试报告 复习pythonunittest 框架的介绍核⼼要素(组成)1. TestCase 测试⽤例, 这个测试⽤例是 unittest 的组成部…...

微服务中的相关概念

Eureka Eureka 是由 Netflix 开发的一个服务发现和注册中心&#xff0c;广泛应用于微服务架构中。Eureka 主要用于管理和协调分布式服务的注册和发现&#xff0c;确保各个服务之间能够方便地找到并通信。它是 Netflix OSS&#xff08;Netflix Open Source Software&#xff09…...

常见的设计模式

设计模式是一套被反复使用的、代码设计经验的总结。它们被用来解决软件开发中的某些常见问题&#xff0c;提高代码的可维护性、可扩展性和重用性。设计模式主要分为三大类&#xff1a;创建型模式、结构型模式和行为型模式。以下是一些常见的设计模式及其简要说明&#xff1a; …...

Camtasia2024中文版最新电脑录屏剪辑神器!

大家好&#xff0c;今天我要安利一个我最近超级喜欢的工具——Camtasia2024中文版&#xff01;这款软件真的太棒了&#xff0c;它让我的视频编辑工作变得更加轻松和高效。如果你也对视频制作感兴趣&#xff0c;那么一定要尝试一下这款神器哦&#xff01; Camtasia2024win-正式…...

【性能优化】表分区实践最佳案例

背景 随着数字化建设的持续深入&#xff0c;企业的业务规模迎来了高速发展&#xff0c;其数据规模也呈现爆炸式增长&#xff0c;如果继续使用传统解决方案&#xff0c;将所有数据存储在一个表中&#xff0c;对数据的查询和维护效率将是一个巨大的挑战&#xff0c;在这个背景下…...

力扣SQL50 项目员工 I ROUND AVG

Problem: 1075. 项目员工 I &#x1f468;‍&#x1f3eb; 参考题解 Code select project_id,ROUND(AVG(e.experience_years),2) as average_years FROMproject as p LEFT JOINemployee as e ONp.employee_id e.employee_id GROUP BYp.project_id;...

nuscenes 数据集学习笔记

目录 数据信息类型: 数据信息类型: Map & Camera(png), Lidar(激光雷达) & Radar(雷达)(pcd), Json 文件结构(以v1.0-mini为例): maps: 存放Map的png文件samples: 存放Camera, Lidar, Radar关键非结构化数据信息, 带标注sweeps: 存放Camera, Lidar, Radar 次要非结构…...

在Windows上用MinGW编译OpenCV项目运行全流程

一、准备软件 OpenCV源码CMake工具MinGW工具链&#xff08;需要选用 posix 线程版本&#xff1a;原因见此&#xff09; 二、操作步骤 官网提供了VC16构建版本的二进制包&#xff0c;但是没有给出GCC编译的版本。所以如果使用MinGW进行构建&#xff0c;那就只能从源码开始构建…...

用Vite基于Vue3+ts+DataV+ECharts开发数据可视化大屏,即能快速开发又能保证屏幕适配

数据可视化大屏 基于 Vue3、Typescript、DataV、ECharts5 框架的大数据可视化&#xff08;大屏展示&#xff09;开发。此项目vue3实现界面&#xff0c;采用新版动态屏幕适配方案&#xff0c;全局渲染组件封装&#xff0c;支持数据动态刷新渲染、内部DataV、ECharts图表都支持自…...

大二学生眼中的Netty?基于Netty实现内网穿透!

爷的开场白 掘金的朋友们大家好&#xff01;我是新来的Java练习生 CodeCodeBond&#xff01; 这段时间呢&#xff0c;博主在学习Netty&#xff0c;想做一个自己感兴趣好玩的东西&#xff0c;那就是内网穿透&#xff01;&#xff01;&#xff08;已经实现主要代理功能但有待优化…...

JavaStringBuffer与StringBuilder

StringBuffer、StringBuilder 文章目录 StringBuffer、StringBuilderStringBuffer和StringBuilder的理解可变性分析对于String对于StringBuilder 常用方法执行效率对比 StringBuffer和StringBuilder的理解 String 不可变的字符序列 StringBuffer 可变的字符序列 JDK1.0声明&…...

云徙科技助力竹叶青实现用户精细化运营,拉动全渠道销售额增长

竹叶青茶以其别具一格的风味与深厚的历史底蕴&#xff0c;一直被誉为茶中瑰宝。历经千年的传承与创新&#xff0c;竹叶青不仅坚守着茶叶品质的极致追求&#xff0c;更在数字化的浪潮中&#xff0c;率先打破传统&#xff0c;以科技力量赋能品牌&#xff0c;成为茶行业的领军者。…...

深度揭秘:深度学习框架下的神经网络架构进化

深度学习框架下的神经网络架构经历了从基础到复杂的显著进化&#xff0c;这一进程不仅推动了人工智能领域的突破性进展&#xff0c;还极大地影响了诸多行业应用。本文旨在深入浅出地揭示这一进化历程&#xff0c;探讨关键架构的创新点及其对现实世界的影响。 引言&#xff1a;…...

MySQL的DML语句

文章目录 ☃️概述☃️DML☃️添加数据☃️更新和删除数据☃️DML的重要性 ☃️概述 MySQL 通用语法分类 ● DDL: 数据定义语言&#xff0c;用来 定义数据库对象&#xff08;数据库、表、字段&#xff09; ● DML: 数据操作语言&#xff0c;用来对数据库表中的数据进行增删改 …...

XCTF-web-easyupload

试了试php&#xff0c;php7&#xff0c;pht&#xff0c;phtml等&#xff0c;都没有用 尝试.user.ini 抓包修改将.user.ini修改为jpg图片 在上传一个123.jpg 用蚁剑连接&#xff0c;得到flag...

R语言AI模型部署方案:精准离线运行详解

R语言AI模型部署方案:精准离线运行详解 一、项目概述 本文将构建一个完整的R语言AI部署解决方案,实现鸢尾花分类模型的训练、保存、离线部署和预测功能。核心特点: 100%离线运行能力自包含环境依赖生产级错误处理跨平台兼容性模型版本管理# 文件结构说明 Iris_AI_Deployme…...

【力扣数据库知识手册笔记】索引

索引 索引的优缺点 优点1. 通过创建唯一性索引&#xff0c;可以保证数据库表中每一行数据的唯一性。2. 可以加快数据的检索速度&#xff08;创建索引的主要原因&#xff09;。3. 可以加速表和表之间的连接&#xff0c;实现数据的参考完整性。4. 可以在查询过程中&#xff0c;…...

【位运算】消失的两个数字(hard)

消失的两个数字&#xff08;hard&#xff09; 题⽬描述&#xff1a;解法&#xff08;位运算&#xff09;&#xff1a;Java 算法代码&#xff1a;更简便代码 题⽬链接&#xff1a;⾯试题 17.19. 消失的两个数字 题⽬描述&#xff1a; 给定⼀个数组&#xff0c;包含从 1 到 N 所有…...

高等数学(下)题型笔记(八)空间解析几何与向量代数

目录 0 前言 1 向量的点乘 1.1 基本公式 1.2 例题 2 向量的叉乘 2.1 基础知识 2.2 例题 3 空间平面方程 3.1 基础知识 3.2 例题 4 空间直线方程 4.1 基础知识 4.2 例题 5 旋转曲面及其方程 5.1 基础知识 5.2 例题 6 空间曲面的法线与切平面 6.1 基础知识 6.2…...

华为OD机试-食堂供餐-二分法

import java.util.Arrays; import java.util.Scanner;public class DemoTest3 {public static void main(String[] args) {Scanner in new Scanner(System.in);// 注意 hasNext 和 hasNextLine 的区别while (in.hasNextLine()) { // 注意 while 处理多个 caseint a in.nextIn…...

【android bluetooth 框架分析 04】【bt-framework 层详解 1】【BluetoothProperties介绍】

1. BluetoothProperties介绍 libsysprop/srcs/android/sysprop/BluetoothProperties.sysprop BluetoothProperties.sysprop 是 Android AOSP 中的一种 系统属性定义文件&#xff08;System Property Definition File&#xff09;&#xff0c;用于声明和管理 Bluetooth 模块相…...

【决胜公务员考试】求职OMG——见面课测验1

2025最新版&#xff01;&#xff01;&#xff01;6.8截至答题&#xff0c;大家注意呀&#xff01; 博主码字不易点个关注吧,祝期末顺利~~ 1.单选题(2分) 下列说法错误的是:&#xff08; B &#xff09; A.选调生属于公务员系统 B.公务员属于事业编 C.选调生有基层锻炼的要求 D…...

Spring Boot+Neo4j知识图谱实战:3步搭建智能关系网络!

一、引言 在数据驱动的背景下&#xff0c;知识图谱凭借其高效的信息组织能力&#xff0c;正逐步成为各行业应用的关键技术。本文聚焦 Spring Boot与Neo4j图数据库的技术结合&#xff0c;探讨知识图谱开发的实现细节&#xff0c;帮助读者掌握该技术栈在实际项目中的落地方法。 …...

Matlab | matlab常用命令总结

常用命令 一、 基础操作与环境二、 矩阵与数组操作(核心)三、 绘图与可视化四、 编程与控制流五、 符号计算 (Symbolic Math Toolbox)六、 文件与数据 I/O七、 常用函数类别重要提示这是一份 MATLAB 常用命令和功能的总结,涵盖了基础操作、矩阵运算、绘图、编程和文件处理等…...