题目
给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那两个整数，并返回他们的数组下标。
你可以假设每种输入只会对应一个答案。但是，数组中同一个元素不能使用两遍。
示例:
给定 nums = [2, 7, 11, 15], target = 9
因为 nums[0] + nums[1] = 2 + 7 = 9
所以返回 [0, 1]解法 1: 暴力枚举
利用双层 for 循环来解决这个问题，枚举出所有的可能性，这是最简单的思维方式。
Golang 解法
func twoSum(nums []int, target int) []int {
for i := range nums {
for j := range nums {
if nums[i]+nums[j] == target && i != j {
return []int{i, j}
}
}
}
return nil
}JavaScript 解法
/**
* @param {number[]} nums
* @param {number} target
* @return {number[]}
*/
var twoSum = function (nums, target) {
for (let i = 0; i < nums.length; i++) {
for (let j = 0; j < nums.length; j++) {
if (nums[i] + nums[j] === target && i !== j) {
return [i, j];
}
}
}
return [];
};时间复杂度是 O(n2)，n 是数组 nums 的长度。
空间复杂度是 O(1)，只用到常数个临时变量。
这种问题一般的优化方案是以空间换时间。
解法 2: 查表法
可以分析得知，如果 target-nums[i] 的值在 nums 中同时存在，那么就可以得到第二个下标 j。这样可以在循环的过程中记录一些值，以省去一层 for 循环。
具体思路是在循环外设置一个 hash 表。当每次循环时，拿 target 减掉当前循环到的元素，得到的值如果在 hash 表中存在，就把 hash 表的值和当前循环的下标返回。每次循环结束时，将当前循环的值作为 hash 表的 key，当前循环的下标作为 hash 表的 value，存入 hash 表。
Golang 解法
func twoSum(nums []int, target int) []int {
m := map[int]int{}
for i, v := range nums {
diff := target - v
if j, ok := m[diff]; ok {
if j != i {
return []int{j, i}
}
}
m[v] = i
}
return nil
}JavaScript 解法
/**
* @param {number[]} nums
* @param {number} target
* @return {number[]}
*/
var twoSum = function (nums, target) {
var map = new Map();
for (let i = 0; i < nums.length; i++) {
let diff = target - nums[i];
let j = map.get(diff);
if (j !== void 0 && i != j) {
return [j, i];
}
map.set(nums[i], i);
}
return [];
};时间复杂度是 O(n)，n 是数组 nums 的长度。
空间复杂度是 O(n)，n 是 hash 表的长度，最短为 1，最长为 nums 的长度。
思考
这道题主要考察的是数组和哈希表的区别，以及以空间换时间的思路。
但在实际场景中还需要考虑 hash 碰撞的问题。