【刷题第五天】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]

二、思路分析：

经典题目，经典得不能再经典了。

拿到这个题目，我第一瞬间就想到了上学期刚学过的求数组中满足 x+y 的一个数，那个题目思路是这样的。

• 首先将数组进行排序，

• 然后双指针扫描，f 为头指针，r 为尾指针如果 arr[f] + arr[r] > z，则 r 前移如果 arr[f] + arr[r] < z，则 f 后移

但这样实现的复杂度较高，我试图寻找 O(n) 的方法。

哈希表

题目中有个关键性信息，不能重复且输出全部。我试图寻找 O(n) 的方法，如果时间复杂度为 O(n) ，那意味着我只会遍历一次。

因此我们建立一个哈希表 hash，key 为当前数值，value 为索引。

• 当遍历到元素 i 时，我们去哈希表中查询是否有 target - arr[i]，如果存在，返回 [hash[arr[i]], i]
  

• 如果不存在，则将 arr[i] = i 压入哈希表，等待它的真命天子。

当然这个题目还有暴力法，就不叙述了，暴力又笨比。

三、AC 代码：

var twoSum = function (nums, target) {  const hash = new Map();  for (let i = 0; i < nums.length; i++) {    if (hash.get(target - nums[i])) {      return [hash.get(target - nums[i]), i];    } else {      map.set(nums[i], i);    }  }};复制代码

四、总结：

刷题断了好几天，难受，加油坚持啊，哇哦哇哦!!!

这个题是个简单题，按理说不能做不出来 O(n) 的想法，但我发现我有点肿了双指针的魔咒，记住哈希表映射的方法吧，球球了。