本题采用了 哈希表 的知识。原题链接

题干

给定一个整数数组 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 放入表中待查。