题解 | #两数之和#

哈希表

哈希表是一种根据关键码（key）直接访问值（value）的一种数据结构，而这种直接访问意味着只要知道key就能在O(1)时间内得到value，因此哈希表常用来统计频率、快速检验某个元素是否出现过等。

此题如何跟哈希表联系起来？

• 设计一个哈希表，键保存原数组中的值，值保存原数组中对应值的下标，将此题的两个数的加法过程转换为目标值减去其中一个数的减法过程。
• 在遍历过程中，检测目标值减去当前值的差是否在哈希表中，如果出现说明该哈希表已经保存过这个值，此时哈希表中的值和当前值的下标就是所求的下标，否则将当前值放入哈希表中。

参考

https://blog.nowcoder.net/n/9a518021ed784832832776f7ecd95fbc?f=comment

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 * 
 * @param numbers int整型一维数组 
 * @param target int整型 
 * @return int整型一维数组
 */
export function twoSum(numbers: number[], target: number): number[] {
    // write code here
    const hash: {[key: number]: number} = {};
    const resIndex: Array<number> = new Array(2);
    let temp: number;

    for (let i = 0; i < numbers.length; ++i) {
        temp = target - numbers[i];
        if (hash.hasOwnProperty(temp)) {
            resIndex[0] = hash[temp] + 1;
            resIndex[1] = i + 1;
            break;
        }
        else {
            hash[numbers[i]] = i;
        }
    }

    return resIndex;
}