001 - 两数之和(two-sum)

Create by jsliang on 2019-05-16 22:19:13
Recently revised in 2019-05-24 11:35:28

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

一 目录

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

目录
一 目录
二 前言
三 解题
3.1 解法 - for()
3.2 解法 - indexOf()
3.3 解法 - Map

二 前言

返回目录

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

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

示例:

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

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

三 解题

返回目录

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

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

3.1 解法 - for()

返回目录

  • 解题代码
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 循环破解。

图

  1. 第一遍过滤 nums 数组,标记为 i
  2. 第二遍再次过滤 nums 数组,标记为 i + 1,因为我们是对数组中的两个数字相加,所以不能重复使用同一个数字。
  3. 判断第二次遍历的数字中,它是否等于 target - nums[i],如果成立就返回两个数字的索引。(并不考虑后面还有可成立的答案)。

3.2 解法 - indexOf()

返回目录

  • 解题代码
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() 寻找除当前 itemindex 之外和 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(),你知道该如何操作么?

3.3 解法 - Map

返回目录

  • 解题代码
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 这个对象。

  1. 它可以通过 set() 的形式,以 [key, value] 的形式保存一组数据。(题目中对应 key 就是存入的 target - nums[i] 值,value 就是索引)
  2. 它可以通过 get() 的形式,获取到传入 key 值对应的 value
  3. 它可以通过 has() 的形式,判断 Map 对象里面是否存储了传入 key 对应的 value

然后,我们遍历 nums 数组。

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


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

图

jsliang 会每天更新一道 LeetCode 题解,从而帮助小伙伴们夯实原生 JS 基础,了解与学习算法与数据结构。

扫描上方二维码,关注 jsliang 的公众号,让我们一起折腾!

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

Copyright © jsliang.top 2019 all right reserved,powered by Gitbook该文件修订时间: 2019-06-14 17:47:18

results matching ""

    No results matching ""