1.两数之和

暴力排序

思路

直接暴力解法，遍历两次数组来进行每一次判断

/**
 * 暴力破解 - 循环遍历
 */

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

复杂度分析

• 时间复杂度：最坏的情况就是要遍历两次数组，时间复杂度也就是 N * N = O(N²)

• 空间复杂度：定义了 i 和 j 两个变量，为 1 + 1， 也就是 O(1)

Map解法

思路

遍历数组，把值存储在一个对象或者 map 里面，每次循环都计算一次是否有这个值

存储的结构最好还是 map ，因为 obj 返回的 0 会判断为 false,直接用 map.has 的方法可以直接返回 boolean

代码

/**
 * 存储一个对象
 * @param {number[]} nums
 * @param {number} target
 * @return {number[]}
 */
export function twoSum(nums: number[], target: number) {
    let map: { [key: number]: number } = {}

    for (let i = 0; i <= nums.length; i++) {
        const num = map[target - nums[i]]
        if (num || num === 0) {
            return [map[target - nums[i]], i]
        } else {
            map[nums[i]] = i
        }
    }
}

/** 上面的 obj 拿到值之后为 0 的情况，需要单独判断 === 0， 用 map 会更好 */
export function twoSum(nums: number[], target: number) {
    let map = new Map()

    for (let i = 0; i < nums.length; i++) {
        if (map.has(target - nums[i])) {
            return [map.get(target - nums[i]), i]
        } else {
            map.set(nums[i], i)
        }
    }

    return null
}

复杂度分析

• 时间复杂度：最坏的情况就是遍历完数组,也就是 O(N)

• 空间复杂度：最坏的情况下就是遍历数组存储所有的变量，也就是 O(N)