LeetCode两数之和-初学C++ 官方哈希解法代码注释-C++代码

简介: LeetCode两数之和-初学C++ 官方哈希解法代码注释-C++代码

题目:


1. 两数之和


难度简单13489收藏分享切换为英文关闭提醒反馈


给定一个整数数组 nums 和一个整数目标值 target,请你在该数组中找出 和为目标值 target  的那 两个 整数,并返回它们的数组下标。


你可以假设每种输入只会对应一个答案。但是,数组中同一个元素在答案里不能重复出现。


你可以按任意顺序返回答案。


示例 1:


输入:nums = [2,7,11,15], target = 9

输出:[0,1]

解释:因为 nums[0] + nums[1] == 9 ,返回 [0, 1] 。

示例 2:


输入:nums = [3,2,4], target = 6

输出:[1,2]

示例 3:


输入:nums = [3,3], target = 6

输出:[0,1]

提示:

2 <= nums.length <= 104
-109 <= nums[i] <= 109
-109 <= target <= 109

只会存在一个有效答案

进阶:你可以想出一个时间复杂度小于 O(n2) 的算法吗?


题解思路:这样我们创建一个哈希表,对于每一个 x,我们首先查询哈希表中是否存在 target - x,然后将 x 插入到哈希表中,即可保证不会让 x 和自己匹配。

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        unordered_map<int, int> hashtable;//定义一个哈希容器
        for (int i = 0; i < nums.size(); ++i) {  //遍历列表nums
            auto it = hashtable.find(target - nums[i]);  //寻找哈希里面是否有target-nums[i]
            if (it != hashtable.end()) {  //hashtable1.end()的返回值超过了hashtable1的最后一个 
            //因此此处是用来判断 是否超过字典
                cout<<it->first<<endl; 
                return {it->second, i};  //(*it).first会得到key,(*it).second会得到value
                //这里哈希表的键是数组中的值,哈希表的值是数组中的索引,因此此处用second来进行调用
            }
            hashtable[nums[i]] = i;  //如果没有 则将这个放入哈希
        }
        return {};
    }
};
相关文章
|
5天前
|
Linux Shell 开发工具
C++ 的 ini 配置文件读写/注释库 inicpp 用法 [ header-file-only ]
这是一个C++库,名为inicpp,用于读写带有注释的INI配置文件,仅包含一个hpp头文件,无需编译,支持C++11及以上版本。该库提供简单的接口,使得操作INI文件变得容易。用户可通过`git clone`从GitHub或Gitee获取库,并通过包含`inicpp.hpp`来使用`inicpp::iniReader`类。示例代码展示了读取、写入配置项以及添加注释的功能,还提供了转换为字符串、双精度和整型的函数。项目遵循MIT许可证,示例代码可在Linux环境下编译运行。
36 0
|
5天前
leetcode代码记录(两数之和
leetcode代码记录(两数之和
11 1
|
5天前
|
算法 C语言 C++
|
5天前
leetcode代码记录(有序数组两数之和
leetcode代码记录(有序数组两数之和
14 0
|
5天前
|
存储 安全 算法
【Linux | C++ 】基于环形队列的多生产者多消费者模型(Linux系统下C++ 代码模拟实现)
【Linux | C++ 】基于环形队列的多生产者多消费者模型(Linux系统下C++ 代码模拟实现)
27 0
|
5天前
|
算法 Linux 数据安全/隐私保护
【Linux | C++ 】生产者消费者模型(Linux系统下C++ 代码模拟实现)
【Linux | C++ 】生产者消费者模型(Linux系统下C++ 代码模拟实现)
13 0
|
5天前
|
存储 算法 数据安全/隐私保护
【C++入门到精通】 哈希结构 | 哈希冲突 | 哈希函数 | 闭散列 | 开散列 [ C++入门 ]
【C++入门到精通】 哈希结构 | 哈希冲突 | 哈希函数 | 闭散列 | 开散列 [ C++入门 ]
8 0
|
5天前
|
存储 Serverless C++
【C++入门到精通】哈希 (STL) _ unordered_map _ unordered_set [ C++入门 ]
【C++入门到精通】哈希 (STL) _ unordered_map _ unordered_set [ C++入门 ]
11 1
|
5天前
|
存储 算法
Leetcode 30天高效刷数据结构和算法 Day1 两数之和 —— 无序数组
给定一个无序整数数组和目标值,找出数组中和为目标值的两个数的下标。要求不重复且可按任意顺序返回。示例:输入nums = [2,7,11,15], target = 9,输出[0,1]。暴力解法时间复杂度O(n²),优化解法利用哈希表实现,时间复杂度O(n)。
22 0
|
5天前
|
C++
【C++】一文深入浅出带你参透库中的几种 [ 智能指针 ]及其背后实现原理(代码&图示)
【C++】一文深入浅出带你参透库中的几种 [ 智能指针 ]及其背后实现原理(代码&图示)