代码随想录-哈希表 | 1两数之和
LeetCode 1-两数之和
题目描述
给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 target 的那两个整数，并返回它们的数组下标。
你可以假设每种输入只会对应一个答案。但是，数组中同一个元素在答案里不能重复出现。
你可以按任意顺序返回答案。
解题思路
判断：
- 暴力解法：两层 for 循环查找，时间复杂度为 O(n2)
- 哈希法：
- 本题需要一个集合存放我们遍历过的元素，然后在遍历数组的时候去询问这个集合，某元素是否遍历过，也就是是否出现在这个集合。因此采用哈希法。
- 本题，不仅要知道元素是否遍历过，还要知道这个元素对应的下标。因此使用
map，key存元素，value存下标。
什么时候使用哈希法？
当我们需要查询一个元素是否出现过，或者一个元素是否在集合里时，就要第一时间想到哈希法。
代码
使用哈希表 Map：2ms，43.8M
class Solution {
public int[] twoSum(int[] nums, int target){
int[] res = new int[2]; // 存储返回的下标
if(nums.length == 0 || nums == null){
return res;
}
Map<Integer, Integer> map = new HashMap<>();
for(int i = 0; i < nums.length; i++){
int temp = target - nums[i]; // 遍历当前元素，并在map寻找是否有匹配的Key
if(map.containsKey(temp)){
res[0] = i;
res[1] = map.get(temp);
break;
}
map.put(nums[i], i); // 如果没有找到匹配对，将其添加到map中
}
return res;
}
}
也可以使用双指针法，之后再看。
复杂度
- 时间复杂度
O(n) - 空间复杂度
O(n)
难点
- 遍历数组存入map后，如何判断其中的哪两个数之和为 target
- 这道题中，我们需要给出一个元素，判断这个元素是否出现过，如果出现过，返回这个元素的下标。map 中的存储结构应为
{key: 数据元素, value: 数组元素对应的下标} - 在遍历数组时，只需要向 map 查询是否有和目前遍历元素匹配的数值，如果有，就找到匹配对；如果没有，就把目前遍历的元素放进 map 中，因为 map 存放的就是我们访问过的元素。
- 这道题中，我们需要给出一个元素，判断这个元素是否出现过，如果出现过，返回这个元素的下标。map 中的存储结构应为
总结
学习到新知识：哈希表的使用场景
- 数组：大小受限制，而且如果元素很少、哈希值太大，会造成内存空间的浪费
- set：set 是一个集合，里面放的元素只能是一个 key。而这道题目，不仅要判断 y 是否存在，还要记录 y 的下标位置，因为要返回 x 和 y 的下标，所以 set 也不能用。
- map：map是一种key value的存储结构。对于本题，可以用key保存数值，用value再保存数值所在的下标。
原文地址：https://blog.csdn.net/qq_44581505/article/details/137953776
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！