LeetCode - 001 - 两数之和（two-sum）

摘要：解法返回目录解题代码执行测试解题思路使用双重循环破解。解法返回目录解题代码执行测试知识点遍历数组，返回遍历项，返回当前索引。

Create by jsliang on 2019-05-16 22:19:13

Recently revised in 2019-05-17 14:22:40

Hello 小伙伴们，如果觉得本文还不错，记得给个 star ， 小伙伴们的 star 是我持续更新的动力！GitHub 地址

LeetCode 攻略地址

不折腾的前端，和咸鱼有什么区别

返回目录

难度：简单

涉及知识：数组、哈希表

题目地址：leetcode-cn.com/problems/tw…

题目内容：

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

你可以假设每种输入只会对应一个答案。但是，你不能重复利用这个数组中同样的元素。

示例:

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

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

返回目录

官方题解：leetcode-cn.com/problems/tw…

解题千千万，官方独一家，上面是官方使用 Java 进行的题解。

小伙伴可以先自己在本地尝试解题，再看看官方解题，最后再回来看看 jsliang 讲解下使用 JavaScript 的解题思路。

返回目录

解题代码：

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

执行测试：

nums：[1, 3, 2, 5, 6]

target: 8

return：

[1, 3]

解题思路：使用双重 for 循环破解。

第一遍过滤 nums 数组，标记为 i。

第二遍再次过滤 nums 数组，标记为 i + 1，因为我们是对数组中的两个数字相加，所以不能重复使用同一个数字。

判断第二次遍历的数字中，它是否等于 target - nums[i]，如果成立就返回两个数字的索引。（并不考虑后面还有可成立的答案）。

返回目录

解题代码：

var twoSum = function(nums, target) {
  let result = [];
  nums.map((item, index) => {
    if (nums.indexOf(target - item) > -1 && nums.indexOf(target - item) != index) {
      result = [index, nums.indexOf(target - item)].sort((a, b) => a > b);
    }
  });
  return result;
};

执行测试：

nums：[4, 3, 2, 5, 6]

target: 8

return：

[2, 4]

知识点：

map()：遍历数组，item 返回遍历项，index 返回当前索引。map() 详细介绍

indexOf()：判断数组中是否存在判断条件中的值。如果存在，则返回第一次出现的索引；如果不存在，则返回 -1。indexOf() 详细介绍

sort()：排序，保持返回数组的数字为顺序排列。sort() 详细介绍

解题思路：

首先，我们开辟一块内存 result。

然后，我们通过 map() 遍历 nums，并使用 indexOf() 寻找除当前 item 的 index 之外和 item 相加之和为 target 的结果。

最后，我们返回查找的最新结果，该结果进行了排序（[4, 2] 的返回通过 sort() 排序变成 [2, 4]）

例如，在上面测试 twoSum([1, 3, 2, 5, 6], 8) 的结果就有：

[1, 3]
[2, 4]
[3, 1]
[4, 2]

我们取最后一次的结果并排序返回，即：[2, 4]

进一步思考：如果我们将 map() 换成 for()，你知道该如何操作么？

返回目录

解题代码：

var twoSum = function(nums, target) {
  let map = new Map();
  for (let i = 0; i < nums.length; i++) {
    if (map.has(nums[i])) {
      return [map.get(nums[i]), i];
    } else {
      map.set(target - nums[i], i);
    }
  }
};

执行测试：

nums：[4, 3, 2, 5, 6]

target: 8

return：

[1, 3]

知识点：

Map：保存键值对。任何值(对象或者原始值) 都可以作为一个键或一个值。Map 详细介绍

解题思路：

首先，我们需要了解 Map 这个对象。

它可以通过 set() 的形式，以 [key, value] 的形式保存一组数据。（题目中对应 key 就是存入的 target - nums[i] 值，value 就是索引）

它可以通过 get() 的形式，获取到传入 key 值对应的 value。

它可以通过 has() 的形式，判断 Map 对象里面是否存储了传入 key 对应的 value。

然后，我们遍历 nums 数组。

最后，我们判断 nums[i] 是否存在于 Map 对象中。没有的话，就存入 target - nums[i] 到 Map 中。有的话，因为上次存入的是 target- nums[i]，有点类似于解题的钥匙，既然我们看到 nums[i] 存在于 Map 中，它是解题的钥匙，所以我们只需要返回 [map.get(nums[i]), i] 这组值即可。

jsliang 广告推送：

也许小伙伴想了解下云服务器

或者小伙伴想买一台云服务器

或者小伙伴需要续费云服务器

欢迎点击 云服务器推广 查看！

jsliang 的文档库 由 梁峻荣 采用 知识共享 署名-非商业性使用-相同方式共享 4.0 国际 许可协议进行许可。
基于github.com/LiangJunron…上的作品创作。
本许可协议授权之外的使用权限可以从 creativecommons.org/licenses/by… 处获得。