Pcrab's blog 


001:两数之和


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

题干

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







:D 获取中...


© - Pcrab - 2022 - Powered by Hexo Theme Quark