leetcode 刷题记：1.two-sum

这是 leetcode 的第一道题目。

问题描述

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

// @algorithm @lc id=1 lang=javascript 
// @title two-sum
// @test([2,7,11,15],9)=[0,1]
// @test([3,2,4],6)=[1,2]
// @test([3,3],6)=[0,1]

解题思路

这道题是要放回两个加数在数组中的下标，而且肯定能在数组中找到答案。

方法一

可以使用双层循环的方式来暴力求解，这样的时间复杂度就是$O(n^2)$。

代码:

// @title two-sum
// @test([2,7,11,15],9)=[0,1]
// @test([3,2,4],6)=[1,2]
// @test([3,3],6)=[0,1]
/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number[]}
 */
const twoSum = function(nums, target) {
    for (let i = 0; i < nums.length; i++) {
        for (let j = 0; j < nums.length; j++) {
            if (i !== j && nums[i] + nums[j] === target) {
                return i > j ? [j, i] : [i, j];
            }
        }
    }
};

方法二

有没有更好的方式？先看看里面最简单的数学问题

$$
x+y=target
$$

其中$x$和$y$是nums中的元素，target已知，那如果我们用个 HashMap 保存已经遍历过的元素$x$与target的差$y$作为key，value中存元素$x$的下标，只要找到剩下的数组中存在$y$，就能返回两者的下标了。

代码:

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number[]}
 */
const twoSum = function(nums, target) {
    const map = new Map(target - nums[0], nums[0]);
    let i = 1;

    while (true) {
        if (map.has(nums[i])) return [nums[i], map.has(nums[i])];
        map.set(target - nums[i], nums[i]);
        i++;
    }
};

如此，我们就能只要遍历一次数组，就能得到想要的结果，时间复杂度就只有$O(n)$。

如果不想使用Map，使用Object也行。据说以前没有Map的时候，Object经常拿来当hashmap用。

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number[]}
 */
const twoSum = function(nums, target) {
    const map = { [target - nums[0]]: 0 };
    let i = 1;
    while (true) {
        if (map[nums[i]] !== undefined) return [nums[i], map[nums[i]]];
        map[target - nums[i]] = i;
        i++;
    }
};