Problem

1
2
3
4
5
6
7
8
9
10
11
12
13
14
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 的下标

1
2
3
4
5
6
7
8
9
10
// 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]

1
2
3
4
5
6
7
8
9
10
11
12
13
// 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

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

1
2
3
4
5
6
7
8
9
10
11
12
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))
1
2
3
4
5
6
7
8
9
10
11
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 []