问题描述
给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那 两个 整数，并返回他们的数组下标。
你可以假设每种输入只会对应一个答案。但是，你不能重复利用这个数组中同样的元素。
实例：
给定 nums = [2, 7, 11, 15], target = 9
因为 nums[0] + nums[1] = 2 + 7 = 9
所以返回 [0, 1]
解决方法
解法一
暴力遍历方法，通过双层遍历，穷尽组合找到两个元素，使之和满足目标值。
原理：双层遍历所有元素，找到 a + b = target 的元素的索引。
时间复杂度为 O(n^2)，空间复杂度为 O(1)。
var twoSum = function(nums, target) {
for (let i = 0; i < nums.length; i++) {
const a = nums[i];
for (let j = i + 1; i < nums.length; i++) {
const b = nums[i];
if (a + b === target) {
return [i, j];
}
}
}
return new Error('there is no answer');
};
解法二
为了快速的查找 target - nums[i] 元素所在的位置，我们可以使用哈希表快速查找元素。比起遍历算法，执行的时间效率为 O(1)。具体实现如下：
/**
* @param {number[]} nums
* @param {number} target
* @return {number[]}
*/
var twoSum = function(nums, target) {
const map = new Map();
nums.forEach((value, index) => {
map.set(value, index);
});
for (let i = 0; i < nums.length; i++) {
const a = nums[i];
const residual_value = target - a;
const j = map.get(residual_value);
if (j !== undefined && j !== i) {
return [i, j];
}
}
return new Error('there is no answer');
};
时间复杂度为 O(n)，空间复杂度为 O(n)。
解法三
仍然是使用哈希表找元素，但是只使用一次哈希。
var twoSum = function(nums, target) {
const map = new Map();
for (let i = 0; i < nums.length; i++) {
const complement = target - nums[i];
if (map.get(complement)) {
return [map.get(complement), i];
}
map.set(nums[i], i);
}
return new Error('there is no answer');
};
