Two Sum

Problem

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].

Solution

1、Brute Force

暴力破解，遍历每个元素 x，查找符合 n = target−x 的值，返回 n, x 的下标

// brute force Runtime: 112 ms 37MB
const len = nums.length;
for (let i = 0; i < len; i++) {
  for (let j =  i+1; j < len; j++) {
    if (nums[j] === target - nums[i]) {
      return [i, j]
    } 
  }
}
return []

2、two-pass hash table

(1) 遍历两次数组，第一次遍历，以元素为 key，索引为 value，生成一份 map

(2) 第二遍遍历, 确定每个元素被目标元素相减所得的值 (target - nums[i]) 是否存在 map 中，这里需要注意 (target - nums[i]) != nums[i]

// two-pass hash table Runtime: 72 ms 37.9MB
const len = nums.length;
const map = new Map()
for (let i = 0; i < len; i++) {
  map.set(nums[i], i) 
}
for (let i = 0; i < len; i++) {
  const complement = target - nums[i]
  if (map.has(complement) && map.get(complement) !== i) {
    return [i, map.get(complement)]
  }
}
return []

3、 One-pass hash table

遍历一遍列表，目标值与当前元素相减得到符合条件的元素，查找字典，如果存在符合条件的键，返回值，否则把该元素作为键，索引作为值存到字典里，重复以上步骤，直到找到对应的两个元素，返回索引列表,若未找到，返回空数组。

class Solution:
    def twoSum(self, nums, target):
        hashmap = {}
        for i, val in enumerate(nums):
            complement = target - val
            if complement in hashmap:
                return [hashmap[complement], i]
            hashmap[val] = i
        return []

    def __init__(self, nums, target):
        print(self.twoSum(nums, target))

const len = nums.length;
const map = new Map();
for (let i = 0; i < len; i++) {
  const complement = target - nums[i];
  if (map.has(complement) && map.get(complement) !== i) {
    return [map.get(complement),i];
  } else {
    map.set(nums[i], i); 
  }
}
return []