二数之和

题目

English

Given an array of integers, return indices of the two numbers such that they add up to a specific target.

You may assume that each input would have exactly one solution, and you may not use the same element twice.

Example:

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

Because nums[0] + nums[1] = 2 + 7 = 9,
return [0, 1].

翻译

一个整数数组，如果数组中的二个数字之和等于特定值，返回这二个数的索引。
假定肯定有解，但是你只能使用每个元素最多一次。
例:

给定数组： nums = [2, 7, 11, 15], 二数之和为：9,

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

详细解答

1. for 循环

标准的做法，第一印象，数组nums中的2数之和等于target，那就穷举，将数组的任意2数相加，判断和是否等于target，是则返回这个数字的索引。
实现如下：

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

该实现方式的时间复杂度为：O(n²)，空间复杂度： O(n)
即使中规中矩的做法，运行时间210ms也击败了50%的已通过代码的执行时间，还不错。下面来优化下

2. Map 实现

ES6为我们提供了Map数据结构。它是一个”value-value”的对应。如果需要“键值对”的数据结构，Map是一个很合适的数据结构。
这里我们先用ES5的方式实现，定义一个对象，将nums的值作对对象的属性，而index作为对象属性所对应的值。

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

该实现方式的时间复杂度为：O(n)，空间复杂度： O(n)

3. 优化版 map 实现

var twoSum = function(nums, target) {
    const map = new Map();
	for (let [index, elem] of nums.entries()) {
		var complement = target - elem
		if (map.has(complement)) {
			return [map.get(complement), index];
		}
		map.set(elem, index);
	}
};