leetcode 之 两数之和

timehorse · · 283 次点击 · · 开始浏览    
这是一个创建于 的文章,其中的信息可能已经有所发展或是发生改变。

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

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

因为 nums[0] + nums[1] = 2 + 7 = 9
所以返回 [0, 1]
链接:https://leetcode-cn.com/problems/two-sum

入门求解思路

这道题最直观最容易想到的就是遍历嘛,也就是暴力求解。其实就是搞组合,从O(n^n/2)的组合中找到和为target的那些个组合。

快速解法:

另外的方法就不是那么显而易见了。

我们一步步的想:

  1. 要找的两个数都在数组中,假如其中一个是A,那么另外一个数B就是target-A。

  2. (A,target-A)均是数组中元素。

  3. 假如我们确定了A,那么另外一个数B(=target-A)其实就已经是确定的了。

  4. 假如我们知道了A,我们能够快速确定的是A、A的下标indexA,以及B。那么我们接下来所要做的就是快速找到B所对应的下标即可。

  5. 数组,我们知道,如果知道一个数的下标索引index,那么我们只要O(1)时间就立即知道该下标所对应的值List[index],那么反过来就难了。知道数组中某个元素的值,那么我们怎么能快速知道它的下标呢?正常就是遍历,需要O(n)时间,还能怎么做呢?

  6. 我们应该想到的是把数组中每个值对应的下标给存起来,这样,每个值对应的下标我们也就立马能知道了。怎么存呢?

  7. 这时,就要利用另一种数据结构:字典。字典有很多种称呼,map,dict,..whatever。我们的做法就是,将数组中的每个元素的值作为字典的key,然后将其下标作为value保存到字典中。

  8. 最后一步是:假如现在有字典中某个元素key是key1,那么另一个元素target-key1也在字典中,则二者对应的value即为结果。

简单代码(golang vs python)

golang

package main

import (
    "fmt"
)

func sumOfNums(numList []int, target int) {
    numMap := make(map[int]int)
    for index, value := range numList {
        numMap[value] = index
    }
    for key, value := range numMap {
        if rvalue, ok := numMap[target-key]; ok {
            fmt.Println(value, rvalue)
        }
    }
}

func main() {
    var numList = []int{2, 3, 5, 7, 11, 13}
    var target = 10
    sumOfNums(numList, target)
}

python

array = [2, 5, 7, 11, 13]
target = 13

def sum_func(array, target):
  map_of_array = {}
  for index, value in enumerate(array):
    map_of_array[value] = index
  
  for key, value in map_of_array.items():
    if target - key in map_of_array.keys():
      print(value, map_of_array[target-key])

sum_func(array, target)

有疑问加站长微信联系(非本文作者)

本文来自:简书

感谢作者:timehorse

查看原文:leetcode 之 两数之和

入群交流(和以上内容无关):加入Go大咖交流群,或添加微信:liuxiaoyan-s 备注:入群;或加QQ群:701969077

283 次点击  
加入收藏 微博
暂无回复
添加一条新回复 (您需要 登录 后才能回复 没有账号 ?)
  • 请尽量让自己的回复能够对别人有帮助
  • 支持 Markdown 格式, **粗体**、~~删除线~~、`单行代码`
  • 支持 @ 本站用户;支持表情(输入 : 提示),见 Emoji cheat sheet
  • 图片支持拖拽、截图粘贴等方式上传