LeetCode 1 Two Sum

Given an array of integers, return indices of the two numbers such that they add up to a specific target.

You may assume that each input would have exactly one solution, and you may not use the same element twice.

Example

Given nums = [2, 7, 11, 15], target = 9,
Because nums[0] + nums[1] = 2 + 7 = 9,
return [0, 1].

解题思路

刚开始感觉遍历所有两个元素的组合来判断是否等于目标值,需要n∗(n−1)/2 步。(O(n^2))

第一次尝试

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number[]}
 */
var twoSum = function(nums, target) {
  for(var i = 0; i < nums.length; i++)
    for(var j = i; j < nums.length; j++)
      if(nums[i] + nums[j] == target)
        return [i,j]
};

测试

// Given nums = [2, 7, 11, 15], target = 9
[0,1]
// Given nums = [2, 8, 11, 15], target = 9
undefined

看起来这种方法应该符合条件,但其实不符合题目,题目说每个元素只能用一次,很明显第一种方法不符合题目(每个元素用了n-1次)

第二次尝试

题目要求每个元素只能用一次,那就意味着大O是O(n). 什么样的的算法可以遍历一遍所有元素判断出来呢?虽然,我想到了应该用map(hash table) 来写,但我对map不熟,看到别人的算法才明白该怎么做。

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number[]}
 */
var twoSum = function(nums, target) {
  var map = {}
  for(var i = 0; i < nums.length; i++){
    var v = nums[i]
    if(map[target - v] >= 0)   //判断target-v是否在map出现过(所有index都是大于等于0的数)
      return [map[target - v], i]
    else map[v]=i //用map储存数字和位置
  }
}

测试

// Given nums = [2, 7, 11, 15], target = 9
[0,1]
// Given nums = [2, 8, 11, 15], target = 9
undefined

这道题的解题关键是对hash table有很好的理解,切入点是每个元素只能用一次 ===> O(n). O(n) 意味着只能用一次for循环和大O是常数的算法,也只剩下hash table 能做到O(1)的search了。