LeetCode Hot100（1.两数之和）

1.两数之和题目给定一个整数数组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]解法一双for循环暴力查找代码class Solution { public: vectorint twoSum(vectorint nums, int target) { for (int i 0; i nums.size(); i) { int nums2 target - nums[i]; for(int ji1;jnums.size();j){ if(nums[j]nums2){ return{i,j}; } } } return{}; } };注意1.vectorint nums引用传递含义传递的是原vector的引用别名不会创建新的副本。优点非常高效节省了拷贝数据所需的时间和内存。2.vectorint nums值传递含义传递的是原vector的完整副本。优点在函数内部修改nums不会影响外部原始数据。缺点每次调用函数都需要复制整个vector。如果数据量大会消耗大量时间和内存在 LeetCode 中极易导致超时Time Limit Exceeded。注意在函数内部对nums的任何修改都会直接改变外部的原始数据。解法二哈希查找哈希表在 C 中std::unordered_map哈希表提供了许多实用的成员函数。以下是在刷题时最常用的几类函数unordered_mapint, int hashtable1. 查找与访问count(key)返回key在 map 中出现的次数。因为 key 是唯一的所以返回值只能是0不存在或1存在。常用于判断某个 key 是否存在。find(key)返回一个迭代器。如果找到指向该元素如果没找到指向end()。at(key)返回 key 对应的 value。如果 key 不存在会抛出异常比直接用[]访问更安全。2. 插入与修改map[key] value如果 key 存在则修改其 value如果 key 不存在则插入新的键值对。这是“两数之和”中最常用的写法。insert({key, value})或emplace(key, value)插入键值对。注意如果 key 已存在它们不会覆盖原有的 value这与[]的行为不同。3. 删除erase(key)删除指定 key 的键值对。4. 状态与容量size()返回 map 中当前有多少个键值对。empty()判断 map 是否为空返回true或false。clear()清空 map 中的所有元素。迭代器在 C 中迭代器Iterator可以理解为一种“智能指针”。它的主要作用是提供一种统一的方式来遍历和访问容器如vector、unordered_map中的元素而不需要暴露容器内部的底层数据结构。1. 迭代器是什么你可以把容器想象成一排储物柜而迭代器就是指向某个具体储物柜的“指针”。通过迭代器你可以找到当前指向的储物柜里的内容。你也可以让迭代器移动例如it指向下一个储物柜。2. 在unordered_map中迭代器指向什么对于unordered_mapint, int它的每一个元素都是一个键值对Key-Value pair。在 C 底层这个键值对被封装在一个std::pair结构中。因此find()返回的迭代器实际上是指向了这个pair结构。3. 如何通过迭代器访问元素既然迭代器指向的是一个pair你就可以通过箭头运算符-来分别获取 Key 和 Valueit-first获取 Key键。it-second获取 Value值。代码class Solution { public: vectorint twoSum(vectorint nums, int target) { unordered_mapint,inthashtable; for(int i0;inums.size();i){ auto it hashtable.find(target-nums[i]); if(it!hashtable.end()){ return{i,it-second}; } else{ hashtable[nums[i]]i; } } return{}; } };需要注意的是在本题中因为要寻找target-nums[i]在哈希表中是否出现过因此将数组的值作为哈希表的键利用find()能达到快查的效果。