下一篇:LeetCode链表相加-Python<二>

题目:https://leetcode-cn.com/problems/two-sum/description/

给定一个整数数组和一个目标值,找出数组中和为目标值的两个数。

你可以假设每个输入只对应一种答案,且同样的元素不能被重复利用。

示例:

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

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

解法一

求差值,判断差值是否在nums数组里

class Solution:
def twoSum(self, nums, target):
"""
:type nums: List[int]
:type target: int
:rtype: List[int]
"""
n = len(nums)
for x in range(n):
b = target-nums[x]
if b in nums:
y = nums.index(b)
if y!=x:
return x,y

时间复杂度:O(n2),空间复杂度:O(1)   (补充:python中list对象的存储结构采用的是线性表,因此其查询复杂度为O(n) 也就是 if b in nums 时间复杂度是O(n))

解法二

求差值、把差值存进字典里作为键、索引作为值,第一次循环理解:d[7]=0 即字典d={7:0},表示为索引0需要数组里值为7的元素配对。 if 判断是否为前面元素所需要配对的值 , 是则返回两个索引值。(补充:nums[x] in d  是判断值是否在字典某个key里面)

class Solution:
def twoSum(self, nums, target):
"""
:type nums: List[int]
:type target: int
:rtype: List[int]
"""
n = len(nums)
#创建一个空字典
d = {}
for x in range(n):
a = target - nums[x]
#字典d中存在nums[x]时
if nums[x] in d:
return d[nums[x]],x
#否则往字典增加键/值对
else:
d[a] = x
#边往字典增加键/值对,边与nums[x]进行对比

时间复杂度:O(1) 、空间复杂度O(n) (补充:dict对象的存储结构采用的是散列表(hash表),其在最优情况下查询复杂度为O(1))

解法三

暴力循环、不多说

class Solution:
def twoSum(self, nums, target):
"""
:type nums: List[int]
:type target: int
:rtype: List[int]
"""
#用len()方法取得nums列表的长度
n = len(nums)
#x取值从0一直到n(不包括n)
for x in range(n):
#y取值从x+1一直到n(不包括n)
#用x+1是减少不必要的循环,y的取值肯定是比x大
for y in range(x+1,n):
#假如 target-nums[x]的某个值存在于nums中
if nums[y] == target - nums[x]:
#返回x和y
return x,y

时间复杂度:O(n2)、空间复杂度:O(1)

执行时间明显多于一和二。

性能:解法二>解法一>解法三 。(补充:不能根据这个图片的执行用时比较,应该从时间复杂度比较)

最新文章

  1. Java 输出流中的flush方法
  2. 洛谷P2412 查单词 [trie树 RMQ]
  3. Sprint1(第三天11.16)
  4. RMAN 备份及策略
  5. SGU 260.Puzzle (异或高斯消元)
  6. 初学jquery遇见的两个小问题!
  7. mysql分表分库
  8. java精度计算代码,指定精确小数位
  9. ubuntu16.04 安装常见问题解决方案------输入法黑框
  10. 多进程IPC与Python支持
  11. 企业级镜像仓库harbor搭建
  12. 2018-2019-2 网络对抗技术 20165316 Exp5 MSF基础应用
  13. 多线程、互斥锁、异步、GIL
  14. version control
  15. Sql Server 数据库表结构,存储过程,视图比较脚本
  16. 前端下载excel打不开求助+解法
  17. 《剑指offer》二叉搜索树的后序遍历序列
  18. PXE:偷梁换柱,成功 启动 centos live
  19. Linux RPM、YUM、APT包管理工具
  20. phpstorm10使用服务激活

热门文章

  1. 2019.02.21 bzoj2829: 信用卡凸包(凸包)
  2. servlet跨域
  3. javascript的常用事件
  4. Codeforces Round #512 E - Vasya and Good Sequences
  5. Alpha阶段项目复审(冲鸭队)
  6. redis之一初识redis
  7. 3.html基础标签:表格
  8. 手动封装on,emit,off
  9. 2017CS231n学习笔记——计算机视觉的概述
  10. JS禁用键盘浏览器退格键