LeetCode 1 | Two Sum 两数之和

题目描述

给定一个整数数组 和一个目标值 ，在该数组中找出和为目标值的那两个整数，并返回他们的数组下标。

例如:

nums = [2, 7, 11, 15]
target = 9

因为 nums[0] + nums[1] = 2 + 7 = 9

所以返回 [0, 1]

分析

最容易想到是暴力解法， 即使用两个循环， 遍历所有可能的情况， 查找两两相加结果是期望值的结果

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number[]}
 */

// 暴力解法
// 时间复杂度：O(n的二次方)
// 空间复杂度：O(1)

var twoSum = function(nums, target) {

    let l = nums.length

    for (let i = 0; i < l;i++) {

        for (let j = i + 1; j < l; j++) {

        // 如果两数相加等于期望值 返回两数的下标

            if (nums[i] + nums[j] === target) {

                return [i, j]

            }

        }

    }

};

这种方式好比两个人对暗号， 每两个人都要互相询问一遍，才能配对，时间消耗大。

为了减少时间复杂度， 可以使用登记册(Hash表)的方式，这是一种用更多的空间 ,换取更快的时间的一种常用法，步骤为先循环一遍，让每个人把自己的暗号和对应索引记录在登记册上。所有人登记完毕后， 再次遍历一遍，从记录完成的Hash表中找到每个人需要对应的暗号，如果找到了，就返回自己的索引和Hash表中对上暗号的索引。

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number[]}
 */

// 两遍Hash表
// 时间复杂度：O(n) (2 * n)
// 空间复杂度：O(n) 所需的额外空间取决于哈希表中存储的元素数量，该表中存储了 n 个元素

var twoSum = function(nums, target) {

    let hash = {}

    // 把数组中每个元素的值和数组索引， 作为key和value, 记录在hash表中
    for (let i=0; i < nums.length; i++) {

        hash[nums[i]] = i

    }

    // 从hash表中取配对结果
    for (let i=0; i < nums.length; i++) {

        // t为当前数组元素满足相加和为target的元素值
        let t = target - nums[i]

        // 如果hash表中有配对值 又不是当前元素自己， 则配对成功
        if (hash[t] >= 0 && hash[t] !== i) {

            return [i, hash[t]]

        }

    }
    
};

hash表登记和配对的过程可以同时进行，如果一个人在Hash表中找到了自己的暗号，则配对成功， 返回Hash表中对应暗号的下标和自己的下标，否则就把自己的暗号登记下来，这样一遍下来就可以对上暗号

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number[]}
 */

// 一遍 Hash表
// 时间复杂度：O(n)
// 空间复杂度：O(n)

var twoSum = function(nums, target) {

    let hash = {}

    for (let i=0; i < nums.length; i++) {

        let t = target - nums[i]

        // hash表中有值 则配对成功返回
        if (hash[t] >= 0) {

            return [hash[t], i]

        }

        // 没找到值， 把自己的值和下标登记在hash表
        hash[nums[i]] = i

    }
};