【LeetCode】1. 两数之和

LeetCode 题目地址：https://leetcode-cn.com/problems/two-sum/description/

题目

给定一个整数数组和一个目标值，找出数组中和为目标值的两个数。

你可以假设每个输入只对应一种答案，且同样的元素不能被重复利用。

示例:

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

因为 nums[0] + nums[1] = 2 + 7 = 9
所以返回 [0, 1]

JavaScript:

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number[]}
 */
var twoSum = function(nums, target) {

};

解答

方法一

获取一个元素之后，向后查找是否有与其相对应的数字，如果没有，找下一个元素。如果有，则返回。

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number[]}
 */
var twoSum = function(nums, target) {
    let len = nums.length;
    for(let i = 0; i < len; i++) {
        for (let j = i + 1; j < len; j++) {
            if(nums[i] + nums[j] === target) {
                return [i,j];
                break;
            }
        }
    }
    return [];
}

方法二

获取一个元素a，我们又知道了两数之和target，所以我们可以通过target - a 的计算，得到我们要找的另外一个数字，这个时候我们在数组中查找就好。

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number[]}
 */
var twoSum = function(nums, target) {
    let n;
    let x;
    let len = nums.length - 1;
    for(let i = 0; i < len; i++) {
        n = target - nums[i]; // 获取满足条件的另一个数字
        x = nums.indexOf(n, i + 1); // 在nums数组中的第 i+1个元素之后，查找是否存在n
        if(x > -1) {
            return [i, x];
        }
    }
    return [];
};

方法三

方法二 中的indexOf其实也算是遍历了一遍数组，遍历数组是很浪费时间的，那么我们有没有什么办法可以快速的查找数据呢？

为了更快速的查找改元素，我们定义一个对象obj，将key定义为数组元素，value定义为该数组元素在数组中定义的下标，例如：

let nums = [2, 7, 11, 15];
将 nums 改写成 obj
let obj = {
    "2" : 0,
    "7" : 1,
    "11" : 2,
    "15" : 3
}

假设我们要数字11在nums数组中所在的位置，只需obj["11"]即可获取。

解题代码如下：

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number[]}
 */
var twoSum = function(nums, target) {
    let len = nums.length;
    let n = {};
    for(let i = 0; i < len; i++) {
        if (n[ target - nums[i] ] !== undefined){
            return [n[ target-nums[i] ], i];
        }
        n[ nums[i] ] = i;
    }
    return [];
};

转载请注明：转自尹小芃槑