本站消息

站长简介/公众号


站长简介:逗比程序员,理工宅男,前每日优鲜python全栈开发工程师,利用周末时间开发出本站,欢迎关注我的微信公众号:幽默盒子,一个专注于搞笑,分享快乐的公众号

  价值13000svip视频教程,python大神匠心打造,零基础python开发工程师视频教程全套,基础+进阶+项目实战,包含课件和源码

  出租广告位,需要合作请联系站长

+关注
已关注

分类  

暂无分类

标签  

暂无标签

日期归档  

2020-07(10)

2020-08(50)

两数之和-python

发布于2021-04-25 20:46     阅读(272)     评论(0)     点赞(26)     收藏(5)



题目描述:

给出一个整数数组,请在数组中找出两个加起来等于目标值的数,

你给出的函数twoSum 需要返回这两个数字的下标(index1,index2),需要满足 index1 小于index2.。注意:下标是从1开始的

假设给出的数组中只存在唯一解

例如:

给出的数组为 {20, 70, 110, 150},目标值为90
输出 index1=1, index2=2

解法一:

简单粗暴,先取第i个值,然后依次用第i个值与后边的每一个值相加,如果等于target则找到了两个索引

  1. def twoSum(self , numbers , target ):
  2. # write code here
  3. if len(numbers)==0:
  4. return []
  5. result = []
  6. for i in range(0,len(numbers)):
  7. for j in range(i+1,len(numbers)):
  8. sum = numbers[i]+numbers[j]
  9. if sum == target:
  10. result.append(i+1)
  11. result.append(j+1)
  12. return result

解法二

先找到temp = target-num1,看temp是否也在list中,需要考虑temp刚好等于num1的情况,则需要如下步骤

  • temp in list,说明有戏
  • list.index(temp)
  1. def get_two():
  2. numbers = [0, 4, 3, 0]
  3. target = 0
  4. if len(numbers) == 0:
  5. return []
  6. result = []
  7. for i in range(0, len(numbers)):
  8. cur = numbers[i]
  9. temp = target - cur
  10. index = -1
  11. if temp in numbers:
  12. if (numbers.count(temp) == 1) & (temp == numbers[i]): # 如果temp出现了一次,且temp刚好等于number[i],则说明找到的是number[i]本身
  13. continue
  14. else:
  15. index = numbers.index(temp, i + 1) # index是从number[i]后边找temp
  16. result = [i + 1, index + 1]
  17. break
  18. print(result)
  19. return result

解法三

用一个字典记录了值的位置,利用字典模拟hash查找

  1. def twoSum2(numbers, target):
  2. hashMap = {}
  3. for index, value in enumerate(numbers):
  4. hashMap[value] = index
  5. for index, value in enumerate(numbers):
  6. j = hashMap.get(target - numbers[index])
  7. if j is not None and j != index:
  8. return [index + 1, j + 1]

 






所属网站分类: 技术文章 > 博客

作者:丸子

链接:https://www.pythonheidong.com/blog/article/953289/da42d4a9f4d3a755e11c/

来源:python黑洞网

任何形式的转载都请注明出处,如有侵权 一经发现 必将追究其法律责任

26 0
收藏该文
已收藏

评论内容:(最多支持255个字符)