leetcode #1 two sum
2017-07-04 本文已影响0人
huntriver
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].
- 题目大意
给你一个整数数组,判断数组内是否存在两个数字的和为给定的目标数字。一个数字不能用两次,并保证一定有解
最直接的思路就是穷举,检查每两个数字的和,时间效率O(n2)
有没有更好的办法呢?答案是肯定的。我们发现其实当确定一个数的时候,另一个数也随之确定了。所以可以用一个hashmap 来记录每个数字对应的位置,并且用map来检查他的“另一半”是否存在。时间效率降为O(n)
/**
* @param {number[]} nums
* @param {number} target
* @return {number[]}
*/
var twoSum = function(nums, target) {
let map={};
for (let i=0;i<nums.length;i++){ //遍历数字
if (map[nums[i]]!==undefined){ //如果当前数字在map中,说明之前有一个与其配对的数字
return [map[nums[i]],i];
}
map[target-nums[i]]=i; //将与该数字配对的数字存入map,值为该数字的index索引
}
};