⭐算法OJ⭐两数之和【哈希表】(C++ 实现)Two Sum

“两数之和”(Two Sum)是一道非常经典的算法题目,几乎是算法入门和面试准备的必做题之一。它的经典性体现在以下几个方面:

1. 算法入门的基础题目

这道题目是许多初学者接触 哈希表(Hash Table)字典(Dictionary) 的第一个应用场景。
它帮助初学者理解如何通过空间换时间,将时间复杂度从暴力解法的 O ( n 2 ) O(n^2) O(n2) 优化到 O ( n ) O(n) O(n)

2. 面试中的高频题目

在技术面试中,这道题目经常被用作考察候选人对哈希表的理解和应用能力。面试官可能会通过这道题目进一步延伸,考察候选人对边界条件、代码实现细节以及优化思路的掌握。

3. 多种解法,适合不同阶段的练习

这道题目有多种解法,适合不同阶段的练习:

  • 暴力解法:双重循环,时间复杂度 O ( n 2 ) O(n^2) O(n2),空间复杂度 O ( 1 ) O(1) O(1)
  • 哈希表优化:时间复杂度 O ( n ) O(n) O(n),空间复杂度 O ( n ) O(n) O(n)
  • 排序 + 双指针:时间复杂度 O ( n l o g n ) O(n log n) O(nlogn),空间复杂度 O ( 1 ) O(1) O(1)(但需要额外空间存储索引)。

通过这些解法,可以逐步提升对算法和数据结构的理解。

4. 问题变种的基石

“两数之和”是许多更复杂问题的基础,例如:

  • 三数之和(3Sum):在数组中找出三个数,使它们的和等于目标值。
  • 四数之和(4Sum):在数组中找出四个数,使它们的和等于目标值。
  • 两数之和 II - 输入有序数组:数组已排序,要求使用双指针解决。
  • 两数之和 IV - 输入二叉搜索树:在二叉搜索树中寻找两数之和。

这些问题都可以从“两数之和”的思路中延伸出来。

5. 实际应用场景

“两数之和”的思想在实际开发中也有广泛应用,例如:

  • 查找匹配项:在数据库中查找满足某种条件的两个记录。
  • 缓存优化:通过哈希表快速查找缓存中的数据。
  • 金融领域:在股票市场中寻找两笔交易,使它们的收益等于目标值。

1. Two Sum

Given an array of integers nums and an integer target, return indices of the two numbers such that they add up to target.
You may assume that each input would have exactly one solution, and you may not use the same element twice.
You can return the answer in any order.

Example 1:

Input: nums = [2,7,11,15], target = 9
Output: [0,1]
Explanation: Because nums[0] + nums[1] == 9, we return [0, 1].

Example 2:

Input: nums = [3,2,4], target = 6
Output: [1,2]

Example 3:

Input: nums = [3,3], target = 6
Output: [0,1]

C++ 代码实现

#include <vector>
#include <unordered_map>using namespace std;vector<int> twoSum(vector<int>& nums, int target) {// 创建一个哈希表,用于存储数字及其对应的索引unordered_map<int, int> num_to_index;// 遍历数组for (int i = 0; i < nums.size(); i++) {int complement = target - nums[i]; // 计算当前数字的补数// 检查补数是否在哈希表中if (num_to_index.find(complement) != num_to_index.end()) {// 如果找到补数,返回补数的索引和当前索引return {num_to_index[complement], i};}// 如果没有找到补数,将当前数字及其索引存入哈希表num_to_index[nums[i]] = i;}// 如果没有找到解(题目保证有解,这里只是占位)return {};
}

代码说明

  • 哈希表的使用:
    • 使用 unordered_map<int, int> 来存储数字及其对应的索引。
    • 键(key)是数组中的数字,值(value)是该数字的索引。
  • 遍历数组:
    • 使用 for 循环遍历数组 nums
    • 对于每个数字 nums[i],计算其补数 complement = target - nums[i]
  • 查找补数:
    • 在哈希表中查找补数 complement
    • 如果找到补数,说明当前数字和补数相加等于目标值,返回它们的索引。
    • 如果没找到补数,将当前数字及其索引存入哈希表。
  • 返回结果:
    • 题目保证有解,因此可以直接返回结果。
    • 如果没有找到解(理论上不会发生),返回空向量。

复杂度分析

  • 时间复杂度:
    • O ( n ) O(n) O(n):只需要遍历一次数组,哈希表的查找和插入操作都是 O ( 1 ) O(1) O(1)
  • 空间复杂度:
    • O ( n ) O(n) O(n):哈希表最多存储 n n n 个元素。

总结

这段代码通过哈希表实现了高效的两数之和查找,时间复杂度为 O ( n ) O(n) O(n),空间复杂度为 O ( n ) O(n) O(n),适合处理大规模数据。

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/34976.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

【sql靶场】第13、14、17关-post提交报错注入保姆级教程

目录 【sql靶场】第13、14、17关-post提交报错注入保姆级教程 1.知识回顾 1.报错注入深解 2.报错注入格式 3.使用的函数 4.URL 5.核心组成部分 6.数据编码规范 7.请求方法 2.第十三关 1.测试闭合 2.列数测试 3.测试回显 4.爆出数据库名 5.爆出表名 6.爆出字段 …

esxi,vcenter6.0安装指导

前言 esxi6.0安装和esxi6.7步骤基本一样&#xff0c;可参考vmware esxi vcenter6.7安装教程&#xff08;dell&#xff09; 环境依赖以及安装包 esxi6.0安装包vcenter6.0安装不同于6.7&#xff0c;6.5通过导入ova模版安装&#xff0c;需要安装在windows server 2008或者windo…

BigFoot Decursive lua

BigFoot Decursive lua 一键驱散脚本 国际化 ogg语音提示 初始化

2024山东大学计算机复试上机真题

2024山东大学计算机复试上机真题 2024山东大学计算机复试机试真题 历年山东大学计算机复试上机真题 历年山东大学计算机复试机试真题 在线评测&#xff1a;传动门&#xff1a;pgcode.cn 最长递减子序列 题目描述 输入数字 n&#xff0c;和 n 个整数&#xff0c;输出该数字…

【AI News | 20250316】每日AI进展

AI Repos 1、ReActMCP 将网络搜索能力集成到AI助手中的一个MCP服务&#xff1a;ReActMCP Web Search&#xff0c;相当于给AI装了个搜索引擎&#xff0c;可以实时查找最新的内容。它基于Exa API执行基本和高级网络搜索&#xff0c;高级搜索比如限制搜索的网站范围、指定日期范围…

【大模型实战篇】使用GPTQ量化QwQ-32B微调后的推理模型

1. 量化背景 之所以做量化&#xff0c;就是希望在现有的硬件条件下&#xff0c;提升性能。量化能将模型权重从高精度&#xff08;如FP32&#xff09;转换为低精度&#xff08;如INT8/FP16&#xff09;&#xff0c;内存占用可减少50%~75%。低精度运算&#xff08;如INT8&#xf…

Unity 笔记:在EditorWindow中绘制 Sorting Layer

在Unity开发过程中&#xff0c;可能会对旧资源进行批量修改&#xff0c;一个个手动修改费人费事&#xff0c;所以催生出了一堆批量工具。 分享一下在此过程中绘制 Sorting Layer 面板的代码脚本。 示意图&#xff1a; 在 EditorGUI 和 EditorGUILayer 中内置了 SortingLayerF…

idea更新git代码报错No Git Roots

idea更新git代码报错&#xff1a; No Git Roots None of configured Git roots are under Git. The configured directory must have ".git directory in it.但是本地项目里是存在.git文件的&#xff0c;就是突然间不能更新代码了 然后尝试重新拉新项目代码提示: Git i…

失败的面试经历(ʘ̥∧ʘ̥)

一.面向对象的三大特性 1.封装&#xff1a;将对象内部的属性私有化&#xff0c;外部对象不能够直接访问&#xff0c;但是可以提供一些可以使外部对象操作内部属性的方法。 2.继承&#xff1a;类与类之间会有一些相似之处&#xff0c;但也会有一些异处&#xff0c;使得他们与众…

qt加载VeloView工程

接上一篇点云软件配置与编译&#xff0c;使用qt加载需要先完成编译。编译完成后到编译目录下lidarview-superbuild\common-superbuild\lidarview\build 找到CmakeCache.txt&#xff0c;如下是我的编译目录。 使用QT6.5.3加载了CmakeCache.txt&#xff0c;QT5.14还加载不了cmake…

Windows Qt动态监测系统分辨率及缩放比变化

前言 Windows 显示设置中&#xff0c;可以修改缩放比&#xff0c;所有界面和文字会同比例放大或缩小&#xff0c;在开发桌面程序时&#xff0c; 实时监测Qt应用程序在不同缩放比例下的表现&#xff0c;可以及时调整程序界面以适应不同显示屏幕的需求。 正文 本文通过Qt相关…

CVE-2017-5645(使用 docker 搭建)

介绍: 是一个与 Apache Log4j2 相关的安全漏洞,属于远程代码执行,它可能允许攻击者通过构造恶意的日志信息 在目标系统上执行任意代码 Log4j2 介绍 Log4j2 是 Apache 的一个日志记录工具,属于 Java 应用的日志框架,它是 Log4j 的升级版,性能更好,功能更多.它被广泛的适用于 J…

交互式可视化进阶(Plotly Dash构建疫情仪表盘)

这里写目录标题 交互式可视化进阶(Plotly Dash构建疫情仪表盘)1. 引言2. 项目背景与意义3. 数据集生成与介绍4. GPU加速在数据处理中的应用5. 交互式仪表盘构建与Plotly Dash6. PyQt GUI集成与美化7. 工程整体架构8. 部分代码实现9. 代码自查与BUG排查10. 总结与展望交互式可…

RabbitMQ(补档)

RabbitMQ 是一个开源的消息队列软件&#xff08;有时也被称为消息代理&#xff09;&#xff0c;它实现了高级消息队列协议&#xff08;AMQP&#xff09;。它主要用于应用程序之间&#xff0c;或者软件组件之间的消息通信。通过使用 RabbitMQ&#xff0c;可以实现异步的、可靠的…

平方矩阵问题

Ⅰ 回字形二维数组 #include <iostream> #include <iomanip> using namespace std; int main(){int n;while(cin>>n,n){for(int i0; i<n;i){for(int j0; j<n; j){int upi, downn-i1, leftj, rightn-j1;cout<<min(min(up,down),min(left,right)…

电子电气架构 --- 智能座舱和车载基础软件简介

我是穿拖鞋的汉子,魔都中坚持长期主义的汽车电子工程师。 老规矩,分享一段喜欢的文字,避免自己成为高知识低文化的工程师: 人生是一场骗局,最大的任务根本不是什么买车买房,也不是及时行乐,这就是欲望,不是理想,是把自己对生命的希望寄托在外物上,正确的做法应该是内…

Qt 通过MSVC编译运行项目

第一步下载Qt 把Qt能选的插件都选上&#xff0c;有的是连接数据库必须得插件&#xff0c;有的是做图表必须得插件&#xff0c;有的是运行MSVC必须得插件&#xff0c;能选尽量都选上。 第二步安装VS2017&#xff0c;当然我们安装2017的目的主要是用C的编译器&#xff0c;这里提…

高效手机检测:视觉分析技术的优势

在当今社会&#xff0c;手机已成为人们日常生活和工作中不可或缺的工具。然而&#xff0c;在某些特定场合&#xff0c;如考场、工作场所等&#xff0c;手机的使用却可能带来负面影响。因此&#xff0c;如何有效监测和防止在这些场合偷用手机的行为&#xff0c;成为了一个亟待解…

Gitee重新远程连接仓库(Linux)

Gitee重新远程连接仓库&#xff08;Linux&#xff09; 因为虚拟机重新安装了一回&#xff0c;所以需要重新和远程仓库连接&#xff0c;在网上找了很久没有找到相关操作&#xff0c;自己实操成功&#xff0c;记录下本博客&#xff0c;帮助有需要的人 确保新虚拟机安装Git 在新虚…