代码随想录刷题-哈希表-两数之和
文章目录
- 两数之和
- 习题
- 暴力解法
- 哈希表
两数之和
本节对应代码随想录中：代码随想录，讲解视频：梦开始的地方，Leetcode：1.两数之和，学透哈希表，map使用有技巧！_哔哩哔哩_bilibili
习题
题目链接：1. 两数之和 - 力扣（LeetCode）
给定一个整数数组 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]
暴力解法
作为 LeetCode 的第一题，题意很明确，就是数组中找和为 target 的两个数，返回他们的下标，并且一定能找到这俩数，并且答案唯一(顺序可以不一样)。
最直接的就是两个 for 循环遍历一个数的时候看看剩余的数里面有没有满足和为 target 的
class Solution {public:vector twoSum(vector& nums, int target) {int size = nums.size();vector res;for (int i = 0; i < size; i++) {for (int j = i + 1; j < size; j++) {if (nums[i] + nums[j] == target) {res.push_back(i);res.push_back(j);return res;}}}return res;}
};
- 时间复杂度：O(n^2)。有两个循环，每个循环运行 n 次，所以总的运行次数为 n * n = n^2
- 空间复杂度：O(n)。创建了长度为 n 的向量 res 来存储结果
可以优化的点
- 其实不用新定义个 res，在返回的时候直接返回
return {i,j}即可，这样空间复杂度就优化成 O(1)
哈希表
上面的暴力解法，就是先遍历一个数，然后再查找剩余的数中有没有 target-nums[i]。那就简化成了在数组中查找一个元素是否存在的问题，所以就可以使用哈希表，因为哈希表查找元素的时间复杂度为 O(1)。
而哈希表有3种：数组、set 和 map，只有 set 和 map 是有 O(1)的 find 函数的。但是 set 只存储 key，而题目要求返回的是下标，set 无法直接得到原来的数的下标。
STL 中有个 distance 函数可以计算两个元素之间的距离，计算找到的元素和 set.begin()之间的距离就可以获得下标吗？
答：这种方法无法获得原有的下标，使用 unordered_set 插入元素时不会保留原始顺序，而是根据哈希表中元素的内部顺序随机排序。也就是说，即使向 set 中添加与 vector 中相同的元素，它们在 set 中的顺序也可能与在 v1中的顺序不同。例如示例中的{2,7,11,15}在 unordered_set 中就会变成{11,7,15,2}的顺序
map 中只有 unordered_map 的查询效率为 O(1)，那么 key 和 value 存什么呢？map 查找的时候查的是 key，而我们要找的是 target-nums[i]即查的是元素本身。那么 key 存的就是数组中的元素，而 value 存的就是对应的下标
我的写法如下
class Solution {public:vector twoSum(vector& nums, int target) {// 创建一个无序哈希表map，key为整数型，value为整数型unordered_map map;// 遍历nums中的元素，将元素值作为键，元素下标作为值插入到map中for (int i = 0; i < nums.size(); i++) {map.insert({nums[i], i});}for (int i = 0; i < nums.size(); i++) {int tmp = target - nums[i];// 判断map中是否含有该差值，如果存在且满足条件则返回下标值if (map.find(tmp) != map.end()) {if (i != map[tmp]) {return {i, map[tmp]};}}}return {};}
};
- 时间复杂度：O(n)。其中，第一个 for 循环遍历整个 nums 数组，需要 n 次操作；第二个 for 循环也遍历整个 nums 数组，需要 n 次操作，哈希表map插入n个元素，需要n次操作。因此总的时间复杂度为O(n+n+n)=O(n)
- 空间复杂度：O(n)。创建了一个哈希表，存储了n个元素，因此空间复杂度为O(n)
而看过题解后，上面的写法可以有优化的地方。我是先将所有元素插入到 map 中，而实际上没有必要先插入所有元素。只需要当没有 target - nums[i]的时候再将当前 nums[i]插入到 map 中，这样也避免了和自己匹配即2*nums[i]=target。如2,7,11,15，target=9，当 i=0时，虽然没有找到 map 中含有7。但是将2插入 map 后，当 i=1即去找 map 中是否含有2的时候就可以找到了。
class Solution {public:vector twoSum(vector& nums, int target) {unordered_map map;for (int i = 0; i < nums.size(); ++i) {auto it = map.find(target - nums[i]);if (it != map.end()) {// 如果找到了，返回这两个元素的下标return {it->second, i};}// 否则将当前的数插入哈希表map[nums[i]] = i;}return {};}
};
- 时间复杂度：O(n)。其中n是nums数组中元素的个数，因为只需要遍历一次nums数组就能找到符合条件的目标值两个元素
- 空间复杂度：O(n)。在最坏情况下，所有的元素都需要插入哈希表中，所以哈希表的空间占用和nums数组大小相同