题目描述

Two Sum

给出一个整数数组，返回数组中两个元素满足相加等于一个目标数字的索引。
可以限定只存在唯一解，且不会使用相同的元素两次(即数组中不存在两个相同的元素)

Given nums = [2, 7, 11, 15], target = 9,

Because nums[0] + nums[1] = 2 + 7 = 9,

return [0, 1].

javascript:

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number[]}
 */
const twoSum = function(nums, target) {

}

From leetcode No.1 Easy (opens new window)

解法

点击查看

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number[]}
 */
const twoSum = function(nums, target) {
    const map = {}
    
    for(let i=0; i<nums.length; i++){
        map[nums[i]] = i
    }
    for(let i=0; i<nums.length; i++){
    	const index = map[target-nums[i]]
        if(index !== undefined && index !== i) //index != i 特殊情况
            return [i, index]
    }
};

总结

两层暴力循环的解法肯定是不推荐的。 但凡是寻找值是否存在，哈希表肯定比循环快。
这里用到哈希的思想，第一步构建哈希表，第二步确认索引。
上述解法用到了两次单循环，参考提交答案最快的解决只用了一次循环。 这里是充分利用了限定条件：存在唯一解，同一元素不会使用两次。
改进如下：

点击查看

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number[]}
 */
const twoSum = function(nums, target) {
    const map = {}
    
    for(let i=0; i<nums.length; i++){
        const index = map[target-nums[i]]
        if(index !== undefined && index !== i)
            return [i, index]
        map[nums[i]] = i
    }
};