题目描述
给定一个整数数组 和一个目标值 ，在该数组中找出和为目标值的那两个整数，并返回他们的数组下标。
例如:
nums = [2, 7, 11, 15]
target = 9
因为 nums[0] + nums[1] = 2 + 7 = 9
所以返回 [0, 1]
分析
最容易想到是暴力解法， 即使用两个循环， 遍历所有可能的情况， 查找两两相加结果是期望值的结果
/**
* @param {number[]} nums
* @param {number} target
* @return {number[]}
*/
// 暴力解法
// 时间复杂度：O(n的二次方)
// 空间复杂度：O(1)
var twoSum = function(nums, target) {
let l = nums.length
for (let i = 0; i < l;i++) {
for (let j = i + 1; j < l; j++) {
// 如果两数相加等于期望值 返回两数的下标
if (nums[i] + nums[j] === target) {
return [i, j]
}
}
}
};
这种方式好比两个人对暗号， 每两个人都要互相询问一遍，才能配对，时间消耗大。
为了减少时间复杂度， 可以使用登记册(Hash表)的方式，这是一种用更多的空间 ,换取更快的时间的一种常用法，步骤为先循环一遍，让每个人把自己的暗号和对应索引记录在登记册上。所有人登记完毕后， 再次遍历一遍，从记录完成的Hash表中找到每个人需要对应的暗号，如果找到了，就返回自己的索引和Hash表中对上暗号的索引。
/**
* @param {number[]} nums
* @param {number} target
* @return {number[]}
*/
// 两遍Hash表
// 时间复杂度：O(n) (2 * n)
// 空间复杂度：O(n) 所需的额外空间取决于哈希表中存储的元素数量，该表中存储了 n 个元素
var twoSum = function(nums, target) {
let hash = {}
// 把数组中每个元素的值和数组索引， 作为key和value, 记录在hash表中
for (let i=0; i < nums.length; i++) {
hash[nums[i]] = i
}
// 从hash表中取配对结果
for (let i=0; i < nums.length; i++) {
// t为当前数组元素满足相加和为target的元素值
let t = target - nums[i]
// 如果hash表中有配对值 又不是当前元素自己， 则配对成功
if (hash[t] >= 0 && hash[t] !== i) {
return [i, hash[t]]
}
}
};
hash表登记和配对的过程可以同时进行，如果一个人在Hash表中找到了自己的暗号，则配对成功， 返回Hash表中对应暗号的下标和自己的下标，否则就把自己的暗号登记下来，这样一遍下来就可以对上暗号
/**
* @param {number[]} nums
* @param {number} target
* @return {number[]}
*/
// 一遍 Hash表
// 时间复杂度：O(n)
// 空间复杂度：O(n)
var twoSum = function(nums, target) {
let hash = {}
for (let i=0; i < nums.length; i++) {
let t = target - nums[i]
// hash表中有值 则配对成功返回
if (hash[t] >= 0) {
return [hash[t], i]
}
// 没找到值， 把自己的值和下标登记在hash表
hash[nums[i]] = i
}
};