给出一个由若干整数组成的数组和一个目标整数,返回两个数组的下标使得它们的值加起来正好等于这个目标整数。
你可以假设这个数组中的每个值都是唯一的,且只存在一对这样的下标(它们对应的值的和等于这个目标值)。
返回的下标组成的数组顺序随意。
案例一:
输入:nums = [2, 7, 11, 15], target = 9
输出:[0, 1]
解释:因为 nums[0] + nums[1] = 9, 所以最终得到的两个下标值 [0, 1]
案例二:
输入:nums = [3, 2, 4], target = 6
输出:[1, 2]
案例三:
输入:nums = [3, 3], target = 6
输出:[0, 1]
限制条件:
- 2 <= nums.length <= 104
- -109 <= nums[i] <= 109
- -109 <= target <= 109
- 仅存在唯一有效的答案
1. 时间复杂度为 O(n^2) 的计算方式
/**
* @param {number[]} nums
* @param {number} target
* @return {number[]}
*/
var twoSum = function(nums, target) {
for(let i = 0; i < nums.length; i++) {
for(let j = i + 1; j < nums.length; j++) {
if(nums[i] + nums[j] === target) {
return [i, j];
}
}
}
};
2. 利用Hashmap 时间复杂度为 O(n) 计算方案
/**
* @param {number[]} nums
* @param {number} target
* @return {number[]}
*/
// O(n) hashmap solution
var twoSum = function(nums, target) {
let map = new Map();
for(let i = 0; i < nums.length; i++) {
if(map.has(target - nums[i])) {
// map.get will get the 1st number index and current number index
return [map.get(target - nums[i]), i];
}
// set the number and its index
map.set(nums[i], i)
}
return [];
}
网友评论