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 的下标
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]
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 []