给定一个整数数组 nums
和一个整数目标值 target
,在该数组中找出和为目标值 target
的两个整数,并返回它们的数组下标。
假设每种输入只会对应一个答案,但是,数组中同一个元素在答案里不能重复出现。
可以按任意顺序返回答案。
示例:
输入:nums = [2,7,11,15], target = 9
输出:[0,1]
解释:因为 nums[0] + nums[1] == 9 ,返回 [0, 1] 。
假设测试数据为:
const upper = 20000;
const nums = Array.from({length: Math.floor(Math.random() * upper + 1)}, () => Math.floor(Math.random() * upper + 1));
const target = Math.floor(Math.random() * upper + 1);
解法一:双重循环
function func1(arr = [], target) {
const {length} = arr;
for (let i = 0; i < length; i++) {
for (let j = i + 1; j < length; j++) {
if (arr[i] + arr[j] === target) {
return [i, j]
}
}
}
return [];
}
func1(nums,target)
解法二:利用 Map
function func2(arr = [], target) {
const map = new Map();
arr.forEach((item, index) => map.set(item, index));
const {length} = arr;
for (let i = 0; i < length; i++) {
const index2 = map.get(target - arr[i]);
if (index2 && Number.isInteger(index2) && index2 !== i) {
return [i, index2]
}
}
return [];
}
func2(nums,target)
结语
两种解法在数组长度为 20000 时性能无明显优劣差异,第二种解法在数组中存在相同值时,会出现 Map
中数据覆盖问题,导致最终结果错误。
来源:力扣(LeetCode)