两数之和

两数之和我相信,大家对这道题目都不陌生,为什么突然说道这道题目呢,是因为有个朋友来问我,如果是你最优的解决方法是什么。
首先,这个两数之和,不是有些人想着的那种,让你求1+1 = 2。
我来举个案例:如果有个数组nums = [2,7,11,15], 求和数target = 9,输出的值是[0,1],因为数组的第一个值和第二个值加起来是9,这就是本章节要说的两数求和。
我们要用js的方式,去写一个方法实现,这个两数之和。当时我的第一反应就是双重for循环,判断,第一次的循环和第二次的循环相加的结果是不是我的目标值,如果是那就return出结果,但是这种方法太浪费时间,过于暴力,有点呆头鹅。
var twoSum = function (nums, target) {
  for (let i = 0; i < nums.length; i++) {
    for (let j = i + 1; j < nums.length; j++) {
      if (nums[i] + nums[j] === target) {
        return [i, j]
      }
    }
  }
}

解析:上面代码的思路,第一次循环,我们直接循环数组nums,然后第二次循环,我们不从0开始,而是从第一次循环的后一个开始,因为你不可能是重复的,当第一次循环的值 + 第二次循环的值,等于我们的目标和的时候,就拿到第一次循环的下标值和第二次循环的下标值了。

上述的方法是可以实现的,但是为了减少时间,我们尽量用一次循环,所以我参考了,别的大佬给出的思路,这个思路,我当时确实没有想到,所以和大家分享一下,可以先看下代码,备注我也写在了里面。
var twoSum = function (nums, target) {
  const prevNums = {}; // 存储出现过的数字,和对应的索引               
  for (let i = 0; i < nums.length; i++) { // 遍历元素   
    const curNum = nums[i]; // 当前元素   
    const targetNum = target - curNum; // 满足要求的目标元素   
    const targetNumIndex = prevNums[targetNum]; // 在prevNums中获取目标元素的索引
    if (targetNumIndex !== undefined) { // 如果存在,直接返回 [目标元素的索引,当前索引]
      return [targetNumIndex, i];
    } else { // 如果不存在,说明之前没出现过目标元素
      prevNums[curNum] = i; // 存入当前的元素和对应的索引
    }
  }
};

解析:这里用到了一次的循环,首先定义了一个空的对象,然后我们进行循环,循环之后,我们可以拿到这个数组中的每一个,也就是2,7,11,15,然后,我们需要的目标数分别就是,7,2,-2,-6,这时候我们就要看之前定义空对象的元素了,看看这个目标数是不是在这个对象里面,如果有,那么我们可以直接拿到符合要求的两个下标值,如果不能的话,我们就将索引存入之前定义的空对象内。很显然,我们第一次循环判断的时候,肯定走的else里面的,那么,此时存入的下标值就是0,就相当于是prevNums = {2:0},然后走下一回,那么此时,targetNumIndex是有值的,是0,我们就直接拿到了目标数组[0,1]

当然了,说到这里,有人会觉得,写的很复杂,有点啰嗦,官方的话是给了个简精版本的,我也给大家看一下,就是你明白了原理之后,简化起来你也能看懂
var twoSum = function (nums, target) {
  let map = {}
  for (let i = 0; i < nums.length; ++i) {
    const rest = target - nums[i];
    if (map[rest] !== undefined) {
      // 注意这里map里面的是下标比较小的值。
      return [map[rest], i]
    }
    map[nums[i]] = i
  }
  return []
}

解析:为什么说是精简版本呢,你会发现,其实就少了几个赋值的步骤,还有就是多了一个如果数组和目标和不一致的话,就返回一个空数组。这个运行过程和上面是一个意思,这里就不再讲一遍了。

最后我看到了另一位大佬的想法,他的想法是合理利用ES6的map数据结构来完成
var twoSum = function (nums, target) {
  var map = new Map()
  for (let i = 0; i < nums.length; i++) {
    x = target - nums[i]
    if (map.has(x)) {
      return [map.get(x), i]
    }
    map.set(nums[i], i)
  }
}

解析:map,有几个用法,首先,我们用map来存放{数组元素值,坐标}这样的键值对,这里我们循环,然后用set方法去存放,每一个值和对应的下标,然后我们用has去判断这个map里面有没有目标元素,如果有的话,我们就能拿到这两个下标,就会用到get,获取到map存放的下标了。基本上来讲的话,都是需要一定的逆向思维去反推得到结论。

好了,到这里,我们基本上就说完了解决这道题目我能想得出来的一些方法,当然咯,为了方便大家日后遇到,或者需要这种方法,我给大家特地,写完整了一些,这些方法你们想用哪个用哪个,能一次循环结束,就不要用两个循环
/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number[]}
 * * 示例:
 * 输入:nums = [2,7,11,15], target = 9
 * 输出:[0,1]
 * 解释:因为 nums[0] + nums[1] == 9 ,返回 [0, 1] 。
 */
var twoSum = function (nums, target) {
  let map = {}
  for (let i = 0; i < nums.length; ++i) {
    const rest = target - nums[i];
    if (map[rest] !== undefined) {
      // 注意这里map里面的是下标比较小的值。
      return [map[rest], i]
    }
    map[nums[i]] = i
  }
  return []
}

ps:分享一首歌,来自小阿七的《从前说》,为什么分享呢,有时候可能不是因为歌曲好听,而是你感同身受,是你有了故事,所以歌曲才富有了色彩吧。

最后编辑于
©著作权归作者所有,转载或内容合作请联系作者
  • 序言:七十年代末,一起剥皮案震惊了整个滨河市,随后出现的几起案子,更是在滨河造成了极大的恐慌,老刑警刘岩,带你破解...
    沈念sama阅读 216,372评论 6 498
  • 序言:滨河连续发生了三起死亡事件,死亡现场离奇诡异,居然都是意外死亡,警方通过查阅死者的电脑和手机,发现死者居然都...
    沈念sama阅读 92,368评论 3 392
  • 文/潘晓璐 我一进店门,熙熙楼的掌柜王于贵愁眉苦脸地迎上来,“玉大人,你说我怎么就摊上这事。” “怎么了?”我有些...
    开封第一讲书人阅读 162,415评论 0 353
  • 文/不坏的土叔 我叫张陵,是天一观的道长。 经常有香客问我,道长,这世上最难降的妖魔是什么? 我笑而不...
    开封第一讲书人阅读 58,157评论 1 292
  • 正文 为了忘掉前任,我火速办了婚礼,结果婚礼上,老公的妹妹穿的比我还像新娘。我一直安慰自己,他们只是感情好,可当我...
    茶点故事阅读 67,171评论 6 388
  • 文/花漫 我一把揭开白布。 她就那样静静地躺着,像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上,一...
    开封第一讲书人阅读 51,125评论 1 297
  • 那天,我揣着相机与录音,去河边找鬼。 笑死,一个胖子当着我的面吹牛,可吹牛的内容都是我干的。 我是一名探鬼主播,决...
    沈念sama阅读 40,028评论 3 417
  • 文/苍兰香墨 我猛地睁开眼,长吁一口气:“原来是场噩梦啊……” “哼!你这毒妇竟也来了?” 一声冷哼从身侧响起,我...
    开封第一讲书人阅读 38,887评论 0 274
  • 序言:老挝万荣一对情侣失踪,失踪者是张志新(化名)和其女友刘颖,没想到半个月后,有当地人在树林里发现了一具尸体,经...
    沈念sama阅读 45,310评论 1 310
  • 正文 独居荒郊野岭守林人离奇死亡,尸身上长有42处带血的脓包…… 初始之章·张勋 以下内容为张勋视角 年9月15日...
    茶点故事阅读 37,533评论 2 332
  • 正文 我和宋清朗相恋三年,在试婚纱的时候发现自己被绿了。 大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
    茶点故事阅读 39,690评论 1 348
  • 序言:一个原本活蹦乱跳的男人离奇死亡,死状恐怖,灵堂内的尸体忽然破棺而出,到底是诈尸还是另有隐情,我是刑警宁泽,带...
    沈念sama阅读 35,411评论 5 343
  • 正文 年R本政府宣布,位于F岛的核电站,受9级特大地震影响,放射性物质发生泄漏。R本人自食恶果不足惜,却给世界环境...
    茶点故事阅读 41,004评论 3 325
  • 文/蒙蒙 一、第九天 我趴在偏房一处隐蔽的房顶上张望。 院中可真热闹,春花似锦、人声如沸。这庄子的主人今日做“春日...
    开封第一讲书人阅读 31,659评论 0 22
  • 文/苍兰香墨 我抬头看了看天上的太阳。三九已至,却和暖如春,着一层夹袄步出监牢的瞬间,已是汗流浃背。 一阵脚步声响...
    开封第一讲书人阅读 32,812评论 1 268
  • 我被黑心中介骗来泰国打工, 没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留,地道东北人。 一个月前我还...
    沈念sama阅读 47,693评论 2 368
  • 正文 我出身青楼,却偏偏与公主长得像,于是被迫代替她去往敌国和亲。 传闻我的和亲对象是个残疾皇子,可洞房花烛夜当晚...
    茶点故事阅读 44,577评论 2 353

推荐阅读更多精彩内容

  • leetcode 两数之和 思路 给定一个整数数组 nums 和一个目标值 target,请你在该数组中找出和为目...
    unique_a311阅读 177评论 0 1
  • 两数之和: 给定一个整数数组 nums 和一个整数目标值 target,请你在该数组中找出 和为目标值 targe...
    吃亏是祸阅读 114评论 0 1
  • 给定一个整数数组 nums 和一个目标值 target,请你在该数组中找出和为目标值的那 两个 整数,并返回他们的...
    timehorse阅读 592评论 0 0
  • 题目链接 => 戳这里 题目描述:给定一个整数数组 nums 和一个目标值 target,请你在该数组中找出和为目...
    沙漠小舟阅读 96评论 0 0
  • 两数之和 题目叙述: 给定一个整数数组 nums 和一个目标值 target,请你在该数组中找出和为目标值的那 两...
    一萍之春阅读 411评论 0 3