0001-Two Sum

题目

两数之和

思路

暴力解法

使用两层遍历来遍历同一个数组，每层元素相加满足条件，则返回结果

求差法

只使用一层遍历，空间换时间：

1. 定义一个 Map 来存储“数组元素:索引”数据
2. 遍历时，如果目标值减去当前值的结果值，能在 Map 找到，则返回结果

代码

暴力解法：

function twoSum(nums: number[], target: number): number[] {
    let res = []
    // 第1层遍历
    for (let i = 0; i < nums.length; i++) {
        const a = nums[i]
        // 第2层遍历
        for (let j = 0; j < nums.length; j++) {
            const b = nums[j]
            // 符合条件时返回索引数组
            if (a + b === target && i !== j) {
                res = [i, j]
            }
        }
    }
    return res;
};

求差法：

function twoSum(nums: number[], target: number): number[] {
    // 定义Map
    const diffs = {}
    const len = nums.length
    // 第1层遍历
    for (let i = 0; i < len; i ++) {
        // 目标值-当前值，如果能结果能在Map检索到，则返回结果
        if (diffs[target - nums[i]] !== undefined) {
            return [diffs[target - nums[i]], i]
        }
        // 如果结果检索不到，则放入Map
        diffs[nums[i]]=i
    }
};