题目

Given an array of integers nums and an integer target, return indices of the two numbers such that they add up to target.

You may assume that each input would have *exactly* one solution, and you may not use the same element twice.

You can return the answer in any order.

example

Input: nums = [2,7,11,15], target = 9
Output: [0,1]
Explanation: Because nums[0] + nums[1] == 9, we return [0, 1].

Input: nums = [3,2,4], target = 6
Output: [1,2]

Input: nums = [3,3], target = 6
Output: [0,1]

我的思路

function twoSum(nums: number[], target: number): number[] {
    // 建立映射表<值, Array<下标>>
    // 用数组是因为可能一个值重复出现
    let map: Map<number, Array<number>> = new Map<number, Array<number>>();
    nums.forEach((value, index) => {
        let arr = map.get(value) || [];
        arr.push(index);
        map.set(value, arr);
    });
    // 开始搜索另一个数是否存在
    for (let i = 0; i < nums.length; i++) {
        let indexs : Array<number> | undefined = map.get(target - nums[i]);
        // 找到下标
        if (indexs != null) {
            // 判断是不是自己加自己
            if ((target - nums[i]) === nums[i]) {
                // 如果是的话 判断是否有多个相同数字
                // 如果没有就下一轮了
                if (indexs.length >= 2) {
                    return [indexs[0], indexs[1]];
                }
            } else {
                // 不是自己加自己 直接返回即可
                return [i, indexs[0]]
            }
        }
    }
    return []
};

最优解

把两处查找优化成边遍历边查找，还可以保证不会出现下标重复的问题QvQ

function twoSum(nums: number[], target: number): number[] {
    // 建立映射表<值, Array<下标>>
    // 第二个用数组是因为可能一个值重复出现
    let map: Map<number, number> = new Map<number, number>();

    for (let i = 0; i < nums.length; i++) {
        let value: number = nums[i];
        let dif: number = target - value;
        if (map.has(dif)) {
            // dif存在就返回
            return [map.get(dif) as number, i];
        } else {
            // dif不存在就set到map里 并继续迭代
            map.set(value, i);
        }
    }
    return [];
};