問題
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].
解釋
輸入 [2,7,11,15], 9
輸出[0, 1]
因?yàn)閍rr[0] + arr[1] = targert
解法
- 雙遍歷，兩個(gè)for循環(huán)。
時(shí)間復(fù)雜度有些高，但是可以被accept - 用hash表和二，空間換時(shí)間公荧。
用數(shù)組的元素做 key年堆，索引做 value 存入數(shù)組丹墨。遍歷時(shí)尋找數(shù)組里有沒有以 target - key 的元素恼除，如果有的話取出下標(biāo)返回即可疾牲。
var twoSum3 = function(nums, target){
if ( !Array.isArray(nums) || Object.prototype.toString.call(target) !== "[object Number]" ) return;
var arr = [],
i,
j,
len = nums.length;
for ( i = 0; i < len; i ++ ){
j = arr[ target - nums[i] ];
if ( j !== undefined ) return [ j, i ];
arr[nums[i]] = i;
}
}
