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

Two Sum

声明:博主为算法新手,博客仅作为个人学习记录

作为新手我的做法
(1)数组nums遍历一遍挑选出小于target的值及其下标,值存入temp,下标存到indices
(2)遍历temp找到符合temp[i]+temp[j]==target的两个值
(3)返回符合要求的两个数字的下标

#include <iostream>
#include <vector>class Solution {
public:std::vector<int> twoSum(std::vector<int>& nums, int target) {std::vector<int> indices={};std::vector<int> temp={};int j = 0;//先遍历一遍挑出小于target的值以及下标 nums=[2,7,11,15]for(size_t i = 0; i <= nums.size(); i++)if(nums[i] < target) {temp.push_back(nums[i]);//挑出值 temp=[2,7]indices.push_back(i);//记录下标 indices=[0,1]j++;}//遍历temp数组两两加和,如果等于target则返回下标for(size_t i=0; i < indices.size(); i++){for(size_t j=0; j < indices.size(); j++)if(temp[i] + temp[j] == target && i != j)return {indices[i], indices[j]};}// If no solution is found, return an empty vector or handle the error as neededreturn {};}
};
int main() {Solution s = Solution();std::vector<int> nums = {2,3,4,7,11,15};int target = 7;std::vector<int> result = s.twoSum(nums, target);if (!result.empty()) {std::cout << result[0] << " " << result[1] << std::endl;} else {std::cout << "No solution found" << std::endl;}return 0;
}

以上代码在一些情况下会出错:
例如:挑出操作中 nums[i] < target 会把–3挑出,而3没有被挑出来导致错误

Approach 1: Brute Force
直接遍历nums数组,外层确定一个数,内层循环找满足要求的另外一个数

#include <iostream>
#include <vector>class Solution {
public:std::vector<int> twoSum(std::vector<int>& nums, int target) {for(int i=0; i < nums.size(); i++){for(int j=i+1; j < nums.size(); j++)//为什么每次都从i+1处开始找?因为上一轮已经找过i和i以前的了且不满足条件if(nums[i] + nums[j] == target)return {i, j};}// If no solution is found, return an empty vector or handle the error as neededreturn {};}
};

大佬的其他解法
Approach 2: Two-pass Hash Table
(1)遍历nums数组并利用map容器同时保存数字及其下标
(2)遍历nums数组查找满足 target - nums[i] 的数字,根据map容器通过数字找到下标
(3)返回下标

#include <iostream>
#include <vector>
#include <unordered_map>
class Solution {
public:std::vector<int> twoSum(std::vector<int>& nums, int target) {//定义map容器std::unordered_map<int, int> temp;int n = nums.size();//遍历nums数组并利用map容器同时保存数字及其下标for (int i = 0; i < n; i++){temp[nums[i]] = i; //将 nums 数组中的第 i 个元素作为键(key),将 i 作为值(value)插入到 temp 这个 map 容器中}//遍历nums数组查找满足 target - nums[i] 的数字,根据map容器通过数字找到下标for (int i = 0; i < n; i++){int result = target - nums[i];//在map容器temp中查找是否有resultif (temp.count(result) && temp[result]!=i) //count函数如果找到值则返回1,否则返回0,要求找到的值其下标不能与减数一致{return {i,temp[result]};}}// If no solution is found, return an empty vector or handle the error as neededreturn {};}
};
int main() {Solution s = Solution();std::vector<int> nums = {-1,0,1,4,7,11,15};int target = 0;std::vector<int> result = s.twoSum(nums, target);if (!result.empty()) {std::cout << result[0] << " " << result[1] << std::endl;} else {std::cout << "No solution found" << std::endl;}return 0;
}

给map容器输入键值对的方式:

Approach 3: One-pass Hash Table
遍历nums的同时将遍历过的nums中的值插入到map容器中,方便后续在map容器中查找

#include <iostream>
#include <vector>
#include <unordered_map>
class Solution {
public:std::vector<int> twoSum(std::vector<int>& nums, int target) {std::unordered_map<int, int> temp;for(int i=0; i < nums.size(); i++){int complement = target - nums[i];//In C++, the find method of an unordered map searches for a key and returns an iterator to the element if it is found. //If the key is not found, it returns an iterator to the end of the map, which is represented by temp.end().if (temp.find(complement) != temp.end()) {  //在temp中寻找已插入值nums数组中的complement值return {temp[complement], i};}temp[nums[i]] = i;}// If no solution is found, return an empty vector or handle the error as neededreturn {};}
};
int main() {Solution s = Solution();std::vector<int> nums = {0,4,-1,7,1,11,15};int target = 0;std::vector<int> result = s.twoSum(nums, target);if (!result.empty()) {std::cout << result[0] << " " << result[1] << std::endl;} else {std::cout << "No solution found" << std::endl;}return 0;


相关文章:

Two Sum

声明&#xff1a;博主为算法新手&#xff0c;博客仅作为个人学习记录 作为新手我的做法 &#xff08;1&#xff09;数组nums遍历一遍挑选出小于target的值及其下标&#xff0c;值存入temp,下标存到indices &#xff08;2&#xff09;遍历temp找到符合temp[i]temp[j]target的两个…...

3.3.2 交易体系构建——缠论操作思路

本节我们基于交易目标(规避下跌趋势,参与上涨趋势)来构建基于上涨趋势的缠论交易体系。建立上涨趋势的缠论交易体系需要以下几个步骤: 识别下跌走势大概率完成的位置 等待出现转折结构 确定交易模型并交易 从概率的角度来说,判断走势结束是个概率事件。为构建成功较高的交…...

[SQL] 事务的四大特性(ACID)

&#x1f384;事务的四大特性 以下就是事务的四大特性&#xff0c;简称ACID。 原子性&#x1f4e2;事务时不可分割的最小操作单元&#xff0c;要么全部成功&#xff0c;要么全部失败。一致性&#x1f4e2;事务完成后&#xff0c;必须使所有的数据都保持一致隔离性&#x1f4e2…...

使用 Three.js 实现流光特效

大家好&#xff01;我是 [数擎AI]&#xff0c;一位热爱探索新技术的前端开发者&#xff0c;在这里分享前端和 Web3D、AI 技术的干货与实战经验。如果你对技术有热情&#xff0c;欢迎关注我的文章&#xff0c;我们一起成长、进步&#xff01; 开发领域&#xff1a;前端开发 | AI…...

Error [ERR_REQUIRE_ESM]: require() of ES Module

报错信息&#xff1a; 【报错】Message.js 导入方式不对&#xff0c;用的是 ES Moudle 的语法&#xff0c;提示使用 import 引入文件 项目开发没有用到 js-message 依赖&#xff0c;是 node-ipc 依赖中用到的 js-message 依赖&#xff0c; node-ipc 中限制 js-message 版本&a…...

沉浸式翻译插件深度评测:打破语言壁垒的黑科技利器

在信息爆炸的时代,语言障碍成为了许多人获取信息的一大难题。尤其是在浏览外文网站、观看外语视频或阅读外文文档时,语言不通往往会让人倍感困扰。然而,一款名为沉浸式翻译的黑科技插件,却以其强大的翻译能力和便捷的使用体验,成为了众多用户打破语言壁垒的首选工具。本文…...

Java 中 HTTP 协议版本使用情况剖析

Java 中 HTTP 协议版本使用情况剖析 一、HTTP/1.1 与 HTTP/2 概述 (一)HTTP/1.1 HTTP/1.1 是广泛应用且成熟的 HTTP 协议版本,它在互联网发展历程中扮演了重要角色。其特点主要包括: 连接方式:默认采用短连接,即每次请求都要建立新的 TCP 连接,请求完成后断开。不过也…...

蓝桥杯学习大纲

&#xff08;致酷德与热爱算法、编程的小伙伴们&#xff09; 在查阅了相当多的资料后&#xff0c;发现没有那篇博客、文章很符合我们备战蓝桥杯的学习路径。所以&#xff0c;干脆自己整理一篇&#xff0c;欢迎大家补充&#xff01; 一、题型分布&#xff1a; 题型分布为填空…...

VSCode ssh远程连接内网服务器(不能上网的内网环境的Linux服务器)的终极解决方案

VSCode ssh远程连接内网服务器&#xff08;不能上网的内网环境的Linux服务器&#xff09; 离线下载vscode-server并安装: 如果远程端不能联网可以下载包离线安装,下载 vscode-server 的 url 需要和 vscode 客户端版本的 commit-id 对应.通过 vscode 面板的帮助->关于可以获…...

【多模态处理篇五】【DeepSeek文档解析:PDF/Word智能处理引擎】

你知道吗?全球每天产生的PDF文档超过10亿份,但90%的上班族还在用复制粘贴的笨办法处理文档!DeepSeek文档解析引擎就像给你的电脑装上了"文档翻译官",能把PDF/Word里的文字、表格、公式甚至排版样式都变成AI能理解的"语言"。举个真实场景:法务小姐姐用…...

STM32-心知天气项目

一、项目需求 使用 ESP8266 通过 HTTP 获取天气数据&#xff08;心知天气&#xff09;&#xff0c;并显示在 OLED 屏幕上。 按键 1 &#xff1a;循环切换今天 / 明天 / 后天天气数据&#xff1b; 按键 2 &#xff1a;更新天气。 二、项目框图 三、cjson作用 https://gi…...

cs106x-lecture14(Autumn 2017)-SPL实现

打卡cs106x(Autumn 2017)-lecture14 (以下皆使用SPL实现&#xff0c;非STL库&#xff0c;后续课程结束会使用STL实现) 1、min Write a function named min that accepts a pointer to a ListNode representing the front of a linked list. Your function should return the …...

基于STM32的智能家居语音系统(单片机毕设)

前言 源代码下载链接&#xff1a; https://download.csdn.net/download/m0_74712453/90071680 需要实物的可以私信博主或者在文章最下方添加好友。 目录 一、项目介绍和演示视频 二、硬件实现 1. 材料材料 2. 原理图和PCB 三、软件实现 1. 代码解析 1.1 main函数 1.2…...

ASP.NET Core 简单文件上传

使用异步 JavaScript 和 XML&#xff08;AJAX&#xff09;进行简单的文件上传&#xff1b;用 C# 编写的服务器端代码。 使用AJAX和ASP.NET Core MVC上传文件再简单不过了。这不依赖于jQuery。此代码允许上传多个文件&#xff0c;并与 .NET Core 3.1、.NET 6和.NET 8兼容。 如果…...

2502C++,C++继承的多态性

构 A{单 向量<串>记;元<类 T>静 空 ff(串&a){清理(记);名向量(a,记);串 b{"---ff---"};打印(b);T::g();} };构 B:公 A{元<类 T>静 空 f(){串 a{"错误.txt"};ff<T>(a);} };构 C:公 A{元<类 T>静 空 f(){串 a{"a12.c…...

【机器学习】13.十大算法之一K均值算法(K-means)聚类详细讲解

【机器学习】13.十大算法之一K均值算法&#xff08;K-means&#xff09;聚类详细讲解 一摘要二个人简介三K-均值聚类&#xff08;K-means&#xff09;3.1-K均值算法的基本原理3.1.1- 聚类分析的目标3.1.2- K - means算法算法原理 四K-means聚类算法的收敛性五证明K均值算法的收…...

Spring扩展点之Mybatis整合模拟

Spring扩展点之Mybatis整合 单独使用MyBaitis模拟整合MyBatis到Spring 单独使用MyBaitis 通过配置文件生成sqlSessionFactory&#xff0c;用sqlSessionFactory开启session。通过session获取到mapper执行对应的sql。 InputStream inputStream Resources.getResourceAsStream(…...

.NET MVC实现电影票管理

.NET MVC&#xff08;Model-View-Controller&#xff09;是微软推出的基于 Model-View-Controller 设计模式的 Web 应用框架&#xff0c;属于 ASP.NET Core 的重要组成部分。其核心目标是通过清晰的分层架构实现 高内聚、低耦合 的开发模式&#xff0c;适用于构建可扩展的企业级…...

自媒体账号管理工具:创作罐头使用指南

创作罐头使用指南 1. 关于创作罐头 创作罐头是免费的一站式自媒体运营工具&#xff0c;支持各大自媒体平台多账号管理、全网爆文库、原创检测、视频一键分发、团队管理、各平台数据分析等功能。 2. 安装与注册 2.1. 如何安装创作罐头 从我们的官网下载并安装软件 www.czgts.…...

基于数据可视化+SpringBoot+安卓端的数字化OA公司管理平台设计和实现

博主介绍&#xff1a;硕士研究生&#xff0c;专注于信息化技术领域开发与管理&#xff0c;会使用java、标准c/c等开发语言&#xff0c;以及毕业项目实战✌ 从事基于java BS架构、CS架构、c/c 编程工作近16年&#xff0c;拥有近12年的管理工作经验&#xff0c;拥有较丰富的技术架…...

conda相比python好处

Conda 作为 Python 的环境和包管理工具&#xff0c;相比原生 Python 生态&#xff08;如 pip 虚拟环境&#xff09;有许多独特优势&#xff0c;尤其在多项目管理、依赖处理和跨平台兼容性等方面表现更优。以下是 Conda 的核心好处&#xff1a; 一、一站式环境管理&#xff1a…...

Unity3D中Gfx.WaitForPresent优化方案

前言 在Unity中&#xff0c;Gfx.WaitForPresent占用CPU过高通常表示主线程在等待GPU完成渲染&#xff08;即CPU被阻塞&#xff09;&#xff0c;这表明存在GPU瓶颈或垂直同步/帧率设置问题。以下是系统的优化方案&#xff1a; 对惹&#xff0c;这里有一个游戏开发交流小组&…...

学校招生小程序源码介绍

基于ThinkPHPFastAdminUniApp开发的学校招生小程序源码&#xff0c;专为学校招生场景量身打造&#xff0c;功能实用且操作便捷。 从技术架构来看&#xff0c;ThinkPHP提供稳定可靠的后台服务&#xff0c;FastAdmin加速开发流程&#xff0c;UniApp则保障小程序在多端有良好的兼…...

DIY|Mac 搭建 ESP-IDF 开发环境及编译小智 AI

前一阵子在百度 AI 开发者大会上&#xff0c;看到基于小智 AI DIY 玩具的演示&#xff0c;感觉有点意思&#xff0c;想着自己也来试试。 如果只是想烧录现成的固件&#xff0c;乐鑫官方除了提供了 Windows 版本的 Flash 下载工具 之外&#xff0c;还提供了基于网页版的 ESP LA…...

Mac软件卸载指南,简单易懂!

刚和Adobe分手&#xff0c;它却总在Library里给你写"回忆录"&#xff1f;卸载的Final Cut Pro像电子幽灵般阴魂不散&#xff1f;总是会有残留文件&#xff0c;别慌&#xff01;这份Mac软件卸载指南&#xff0c;将用最硬核的方式教你"数字分手术"&#xff0…...

ElasticSearch搜索引擎之倒排索引及其底层算法

文章目录 一、搜索引擎1、什么是搜索引擎?2、搜索引擎的分类3、常用的搜索引擎4、搜索引擎的特点二、倒排索引1、简介2、为什么倒排索引不用B+树1.创建时间长,文件大。2.其次,树深,IO次数可怕。3.索引可能会失效。4.精准度差。三. 倒排索引四、算法1、Term Index的算法2、 …...

C++ 求圆面积的程序(Program to find area of a circle)

给定半径r&#xff0c;求圆的面积。圆的面积应精确到小数点后5位。 例子&#xff1a; 输入&#xff1a;r 5 输出&#xff1a;78.53982 解释&#xff1a;由于面积 PI * r * r 3.14159265358979323846 * 5 * 5 78.53982&#xff0c;因为我们只保留小数点后 5 位数字。 输…...

(转)什么是DockerCompose?它有什么作用?

一、什么是DockerCompose? DockerCompose可以基于Compose文件帮我们快速的部署分布式应用&#xff0c;而无需手动一个个创建和运行容器。 Compose文件是一个文本文件&#xff0c;通过指令定义集群中的每个容器如何运行。 DockerCompose就是把DockerFile转换成指令去运行。 …...

6.9-QT模拟计算器

源码: 头文件: widget.h #ifndef WIDGET_H #define WIDGET_H#include <QWidget> #include <QMouseEvent>QT_BEGIN_NAMESPACE namespace Ui { class Widget; } QT_END_NAMESPACEclass Widget : public QWidget {Q_OBJECTpublic:Widget(QWidget *parent nullptr);…...

echarts使用graphic强行给图增加一个边框(边框根据自己的图形大小设置)- 适用于无法使用dom的样式

pdf-lib https://blog.csdn.net/Shi_haoliu/article/details/148157624?spm1001.2014.3001.5501 为了完成在pdf中导出echarts图&#xff0c;如果边框加在dom上面&#xff0c;pdf-lib导出svg的时候并不会导出边框&#xff0c;所以只能在echarts图上面加边框 grid的边框是在图里…...