1. 两数之和

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

 你可以假设每种输入只会对应一个答案。但是，数组中同一个元素不能使用两遍。

 示例:

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

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

 所以返回 [0, 1]

个人解法——暴力法双循环（leetcode跑分通过——运行时间：144ms,内存消耗：38.4M）

时间复杂度：O(n*n), n为数组元素数量。最坏情况下数组中任意两个数都要被匹配一次

空间复杂度：O(1)

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

leetcode官方题解法：哈希表

相较于暴力法，使用哈希表的方式优化的点在于对于target -nums[i]对应的索引遍历

思路：遍历 nums[]，然后把 target - nums[i] 作为key，把 i 作为 value 存入对象，遍历nums的同时尝试返回对象中target - nums[i]对应的value

/** * @param {number[]} nums * @param {number} target * @return {number[]} */ var twoSum = function (nums, target) { let map = {}; // nums[i]作为key， i作为value let i = 0; // 遍历 nums 的索引 while (i < nums.length) { if (map[target - nums[i]] !== undefined) { // 遍历 nums 的同时尝试在map中寻找target-nums[i] return [i, map[target - nums[i]]]; } map[nums[i]] = i; i++; } };

此种方法的优点在于少一次遍历，速度快，缺点在于多使用了空间在存储map，最差的情况下需要将整个nums存进map

时间复杂度为：O(n)

空间复杂度为： O(n)

leetcode跑分如下：运行时间（84ms），内存消耗（38.9M）

评论区大神写法：

使用了JS中数组的reduce方法，在下一篇博文中介绍reduce的学习

/** * @param {number[]} nums * @param {number} target * @return {number[]} */ var twoSum = function (nums, target) { return nums.reduce((p, v, i, ar) => p[v] !== undefined && ar.splice(1) && [p[v], i] || (i === p['l'] ? [] : p[target - v] = i, p), {l: nums.length - 1}); };