Leetcode 1. Two Sum

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]
Output: Because nums[0] + nums[1] == 9, we return [0, 1].

解法1 嵌套循环直接搜索

function twoSum(nums: number[], target: number): number[] {
    for(let i = 0; i < nums.length - 1; ++i){
        for(let j = i + 1; j < nums.length; ++j){
            if(nums[i] + nums[j] == target){
                return [i, j]
            }
        }
    }
    return []
};

解法2 使用map进行标记

map中的键表示的是已经被搜索过的数与target产生的差，map的值表示的是产生该差的位置。

对于数组中的每个数，首先要检测map中是否有这个数，若存在则说明这个数可以与之前检测过的数构成target，若不存在则将该数与target产生的差和index存入map，用于后续寻找。

function twoSum(nums: number[], target: number): number[] {
    const map : Map<number, number> = new Map()
    
    for(let i = 0; i < nums.length; ++i){
        if(map.has(nums[i])){
            return [map.get(nums[i]), i]
        }else{
            map.set(target - nums[i], i)  
        }
    }
    return []
};