刷力扣1-两数之和

刷力扣1-两数之和

题目描述：

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

你可以假设每种输入只会对应一个答案。但是，数组中同一个元素不能使用两遍。

示例:

给定 nums = [2, 7, 11, 15], target = 9

因为 nums[0] + nums[1] = 2 + 7 = 9

所以返回 [0, 1]

哈希数据结构总共有三种方法，一个是数组，一个是set集合，还有一个是map。这道题力扣中需要的数据量比较大，如果用数组的话，万一元素很少，哈希值太大会造成内存的浪费；

而如果用set，set只能放置key，只能用于查找元素是否存在其中，但这道题需要你在查找key的同时还要返回下标值。

这时候就需要用到键值对的存储结构map，map里面的键key可以用来存储元素值，value用来存储下标，这样就可以在既知道元素的同时也能知道他们的下标是多少。

思路：

我们可以用一次遍历数组，取一个元素x，如果target-x在map中，那么就可以把这两个数字的下标赋给一个新的数组；反之如果target-x不在map中，我们可以把x以{key：x，value：i}的形式，存储在map结构中，直到与它匹配的元素值出现。

代码：

class Solution { public int[] twoSum(int[] nums, int target) { int[] res = new int[2]; //用来存放两个元素值下标的数组 if(nums == null || nums.length == 0){ return res; } Map map = new HashMap<>(); //新建一个map哈希结构 for(int i = 0; i < nums.length;i++){ //遍历数组元素 int temp = target-nums[i]; //存放target-x的元素值 if(map.containsKey(temp)){ //如果target-x在map中，返回他俩下标 res[1] = i; res[0] = map.get(temp); } map.put(nums[i],i); //不存在的话，把{key：x，value：i}对应形式存放map中 } return res; }}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。