01 题目：两数之和

链接：https://leetcode-cn.com/problems/two-sum

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

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

示例:

给定 nums = [2, 7, 11, 15], target = 9
.
因为 nums[0] + nums[1] = 2 + 7 = 9
所以返回 [0, 1]

02 解析

暴力法：双循环时间复杂度为O(n²) 超时不予讨论

hash法：hash表将循环过的值，只要对比在不在表中，所以nums只要遍历一次，时间复杂度为O(n)
another_num 是把另一个数求出来，在hashmap中查找
Line 17：hashmap字典保存的key值是num，value值是index
以输入twoSum([2,7,11,15,14],26)为例： 我们在遍历到11的时候，hashmap中没存15的值，所以到15的时候，才能找到hashmap中有11值，符合要求，才return

这也是为什么return的 hashmap[another_num] 在前， index 在后！

another_num是已存在hashmap中的，所以在前面（小的下标），index只能是后面遍历到的数（大的下标）

03 代码

# 1.暴力法# def twoSum(nums, target):    #     for i in range(len(nums)):#         for j in range(i+1,len(nums)):#             if nums[i] + nums[j] == target:#                 return [i,j]#     return []# 2.hash表def twoSum(nums, target):    hashmap = {
   }    for index,num in enumerate(nums):	# 遍历nums        another_num = target-num   	 	# 另一个数        if another_num in hashmap:            print("find it! Now index=%d,num=%d,another_num=%d"%(index,num,another_num))            return [hashmap[another_num],index]        hashmap[num] = index        print(hashmap)    return Noneright_index = twoSum([2,7,11,15,14],26)print(right_index)

输出：{
   2: 0}{
   2: 0, 7: 1}{
   2: 0, 7: 1, 11: 2}find it! Now index=3,num=15,another_num=11[2, 3]

转载地址：http://fujii.baihongyu.com/

你可能感兴趣的文章

ES7的Async/Await

查看>>

React Native WebView组件实现的BarCode（条形码）、(QRCode)二维码

Immutable.js 以及在 react+redux 项目中的实践

react-native 自定义倒计时按钮

查看>>

19 个 JavaScript 常用的简写技术

查看>>

ES6这些就够了

查看>>

微信小程序：支付系列专辑（开发指南+精品Demo）