本题采用了 哈希表 的知识。原题链接
题干
给定一个整数数组
nums
和一个整数目标值target
,请你在该数组中找出 和为目标值target
的那 两个 整数,并返回它们的数组下标。你可以假设每种输入只会对应一个答案。但是,数组中同一个元素在答案里不能重复出现。
你可以按任意顺序返回答案。
提示:
- 只会存在一个有效答案
题解
首先,根据提示,写出一些边界条件:
function isLegalNumber(num: number): boolean {
if (-1e9 > num || 1e9 < num) {
return false;
}
return true;
}
在每次从数组中取出数字时,通过该条件判断是否直接返回空数组 []
。
另外,在函数最开始时再判断一下数组的长度。
// 边界条件
if (2 > nums.length || 1e4 < nums.length || !isLegalNumber(target)) {
return [];
}
暴力求解
最简单的一种方法,但是需要 for
循环遍历 nums
数组来找到对应的答案。
function twoSum(nums: number[], target: number): number[] {
// 边界条件
if (2 > nums.length || 1e4 < nums.length || !isLegalNumber(target)) {
return [];
}
for (const [outerIndex, outerNum] of nums.entries()) {
if (!isLegalNumber(outerNum)) {
return [];
}
for (const [innerIndex, innerNum] of nums.slice(outerIndex + 1).entries()) {
if (!isLegalNumber(innerNum)) {
return [];
}
if (outerNum + innerNum === target) {
return [outerIndex, innerIndex + outerIndex + 1];
}
}
}
return [];
}
这样虽然非常简单,但是需要的时间复杂度太高,需要进行优化。
哈希表
这时就需要使用到哈希表了。本题需要快速根据一个元素找到数组中的另一个匹配的元素,而这种一对一的匹配很自然地想到了使用哈希表这一 K-V
结构。使用哈希表可以将这一过程的
时间复杂度从
function twoSum(nums: number[], target: number): number[] {
// 边界条件
if (2 > nums.length || 1e4 < nums.length || !isLegalNumber(target)) {
return [];
}
const table = new Map<number, number>();
for (const [index, num] of nums.entries()) {
if (!isLegalNumber(num)) {
return [];
}
const prevIndex = table.get(target - num);
if (prevIndex !== undefined) {
return [prevIndex, index];
} else {
table.set(num, index);
}
}
return [];
}
通过哈希表存储已经遍历过的元素,这样在查找当前元素所需要的 target - num
时,只需要 key
,自身的 index
作为 value
放入表中待查。

This work is licensed under a Creative Commons Attribution-NonCommercial-ShareAlike 4.0 International License.