使用python实现两数之和的画解算法

题目描述

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

你可以假设每种输入只会对应一个答案。但是,数组中同一个元素在答案里不能重复出现。

你可以按任意顺序返回答案。

示例 1:

输入:nums = [2,7,11,15], target = 9

输出:[0,1]

解释:因为 nums[0] + nums[1] == 9 ,返回 [0, 1] 。

示例 2:

输入:nums = [3,2,4], target = 6

输出:[1,2]

示例 3:

输入:nums = [3,3], target = 6

输出:[0,1]

问题分析

1.暴力求解

两层循环,外层循环枚举(或称作选中一个标杆),内层循环从枚举值之后开始遍历,计算两数的和是否等于target。

如果找到了两个数,那么返回这两个数的下标。

for(int i = 0; i < n - 1; ++i) {
    for(int j = i + 1; j < n; ++j ) {
        if nums[i] + nums[j] == target
        ...
    }
}

暴力求解的算法时间复杂度为指数级,也就是O(n^2)

分析暴力求解,我们发现存在重复搜索的情况,也就是对数组中的部分数据搜索了多次。

那如何只对数组中的数据搜索1次(或常数级),然后求解呢?

我们知道,寻找一个数是否存在,最快的方法是通过hash表,在O(1)的时间复杂度之内就可以判断是否存在某个数。

2.哈希表求解

可对数组遍历一次,然后将数据存入hash表,然后再遍历一次数组

查找 target - currentdata 是否存在hash表中,如果存在,那么我们就寻找到了两个数。

题目要求我们返回数组的下标,那么我们的hash表的key是数组元素的值,value是下标。

  • 这种方法在最坏的情况下,对数组遍历了2次,也就是算法的时间复杂度是O(2n),去掉前导系数是O(n),虽然是相比暴力求解,算法的时间复杂度降低了,但是还有优化的空间。
  • 在遍历数组并将数据放入hash表的同时,我们也可以find(target - currentdata)是否存在,如果存在那么就找到了满足条件的两个数。

find(9-4), 存在那返回这两个数的下标,如果不存在,那么将 4 放入hash表。

find(9-6), 存在那返回这两个数的下标,如果不存在,那么将 6 放入hash表。

在遍历到元素5的时候,我们find(9-5),找到了这两个数。

动画演示下这个过程

代码实现

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        hashtable = dict()
        for i, num in enumerate(nums):
            # ② map中查找是否有 target - curvalue的数据
            if target - num in hashtable:
                return [hashtable[target - num], i]
            # ① 数组中的每个数放入map中
            hashtable[nums[i]] = i
        return []

以上就是使用python实现两数之和的画解算法的详细内容,更多关于python实现两数之和的画解算法的资料请关注我们其它相关文章!

时间: 2021-08-28

Python 经典算法100及解析(小结)

1:找出字符串s="aaabbbccceeefff111144444"中,字符出现次数最多的字符 (1)考虑去重,首先将字符串进行过滤去重,这样在根据这些字符进行循环查询时,将会减少循环次数,提升效率.但是本人写的代码较为臃肿,有更好的希望留言评论 str = 'a1fsfs111bbbcccccvvvvvnnnnboooooosssnb' class Countvalue(): def countvalue(self, str1): ''' 利用set自身的去重功能 :param s

Python实现各种排序算法的代码示例总结

在Python实践中,我们往往遇到排序问题,比如在对搜索结果打分的排序(没有排序就没有Google等搜索引擎的存在),当然,这样的例子数不胜数.<数据结构>也会花大量篇幅讲解排序.之前一段时间,由于需要,我复习了一下排序算法,并用Python实现了各种排序算法,放在这里作为参考. 最简单的排序有三种:插入排序,选择排序和冒泡排序.这三种排序比较简单,它们的平均时间复杂度均为O(n^2),在这里对原理就不加赘述了.贴出来源代码. 插入排序: def insertion_sort(sort_lis

详解用python实现简单的遗传算法

今天整理之前写的代码,发现在做数模期间写的用python实现的遗传算法,感觉还是挺有意思的,就拿出来分享一下. 首先遗传算法是一种优化算法,通过模拟基因的优胜劣汰,进行计算(具体的算法思路什么的就不赘述了).大致过程分为初始化编码.个体评价.选择,交叉,变异. 遗传算法介绍 遗传算法是通过模拟大自然中生物进化的历程,来解决问题的.大自然中一个种群经历过若干代的自然选择后,剩下的种群必定是适应环境的.把一个问题所有的解看做一个种群,经历过若干次的自然选择以后,剩下的解中是有问题的最优解的.当然,只

Python常用算法学习基础教程

本节内容 算法定义 时间复杂度 空间复杂度 常用算法实例 1.算法定义 算法(Algorithm)是指解题方案的准确而完整的描述,是一系列解决问题的清晰指令,算法代表着用系统的方法描述解决问题的策略机制.也就是说,能够对一定规范的输入,在有限时间内获得所要求的输出.如果一个算法有缺陷,或不适合于某个问题,执行这个算法将不会解决这个问题.不同的算法可能用不同的时间.空间或效率来完成同样的任务.一个算法的优劣可以用空间复杂度与时间复杂度来衡量. 一个算法应该具有以下七个重要的特征: ①有穷性(Fin

Linux学习基础教程

Linux学习基础 1.什么是Linux?  准确的说,是指Linux的kernel(系统的核心程序),其内核版权属于Linus Torvalds,在GPL(GNU General Public License)版权协议下发行, 任何人都可以自由的复制(copy), 修改(change), 套装分发(distribute),销售,但是不可以在分发时加入任何限制, 而且所有原码必须是公开的,所以任何人都可以无偿取得所有执行文件和原代码.  对于Linux用户和系统管理员来说,Linux是指包含Li

python常见排序算法基础教程

前言:前两天腾讯笔试受到1万点暴击,感觉浪费我两天时间去牛客网做题--这篇博客介绍几种简单/常见的排序算法,算是整理下. 时间复杂度 (1)时间频度一个算法执行所耗费的时间,从理论上是不能算出来的,必须上机运行测试才能知道.但我们不可能也没有必要对每个算法都上机测试,只需知道哪个算法花费的时间多,哪个算法花费的时间少就可以了.并且一个算法花费的时间与算法中语句的执行次数成正比例,哪个算法中语句执行次数多,它花费时间就多.一个算法中的语句执行次数称为语句频度或时间频度.记为T(n). (2)时间复

Python基础教程之内置函数locals()和globals()用法分析

本文实例讲述了Python基础教程之内置函数locals()和globals()用法.分享给大家供大家参考,具体如下: 1. 这两个函数主要提供,基于字典的访问局部变量和全局变量的方式. python 使用叫做名字空间的东西来记录变量的轨迹.名字空间是一个字典 ,它的键就是字符串形式的变量名字,它的值就是变量的实际值. 名字空间可以像 Python 的 dictionary 一样进行访问. 在一个 Python 程序中的任何一个地方,都存在几个可用的名字空间. 每个函数都有着自已的名字空间,叫做

Python KNN分类算法学习

本文实例为大家分享了Python KNN分类算法的具体代码,供大家参考,具体内容如下 1.KNN分类算法 KNN分类算法(K-Nearest-Neighbors Classification),又叫K近邻算法,是一个概念极其简单,而分类效果又很优秀的分类算法. 他的核心思想就是,要确定测试样本属于哪一类,就寻找所有训练样本中与该测试样本"距离"最近的前K个样本,然后看这K个样本大部分属于哪一类,那么就认为这个测试样本也属于哪一类.简单的说就是让最相似的K个样本来投票决定. 这里所说的距

Python画图学习入门教程

本文实例讲述了Python画图的基本方法.分享给大家供大家参考,具体如下: Python:使用matplotlib绘制图表 python绘制图表的方法,有个强大的类库matplotlib,可以制作出高质量的2D和3D图形,先记录一下,以后慢慢学习. matplotlib下载及API手册地址:http://sourceforge.net/projects/matplotlib/files/matplotlib/ 数学库numpy下载及API手册地址:http://www.scipy.org/Dow

Python Flask基础教程示例代码

本文研究的主要是Python Flask基础教程,具体介绍如下. 安装:pip install flask即可 一个简单的Flask from flask import Flask #导入Flask app = Flask(__name__) #创建一个Flask实例 #设置路由,即url @app.route('/') #url对应的函数 def hello_world(): #返回的页面 return 'Hello World!' #这个不是作为模块导入的时候运行,比如这个文件为aa.py,

python基础教程项目五之虚拟茶话会

几乎在学习.使用任何一种编程语言的时候,关于socket的练习从来都不会少,尤其是会写一些局域网的通信的东西.所以书上的这个项目刚好可以练习一下socket编程. 这个练习的整体思路首先有一个聊天的服务器,这个服务器的功能主要是提供客户端socket的连接.存储每个客户端的连接session,处理每个连接发送的消息.解析客户端发送的数据.就这些,至于客户端方面不需要写代码,用系统的telnet工具即可. 我觉得有了上面的分析,剩下的这个程序就没有什么说的了,当然,除了那两个把socket封装的类

python基础教程项目四之新闻聚合

<python基础教程>书中的第四个练习,新闻聚合.现在很少见的一类应用,至少我从来没有用过,又叫做Usenet.这个程序的主要功能是用来从指定的来源(这里是Usenet新闻组)收集信息,然后讲这些信息保存到指定的目的文件中(这里使用了两种形式:纯文本和html文件).这个程序的用处有些类似于现在的博客订阅工具或者叫RSS订阅器. 先上代码,然后再来逐一分析: from nntplib import NNTP from time import strftime,time,localtime f

python基础教程项目三之万能的XML

这个项目的名称与其叫做万能的XML不如叫做自动构建网站,根据一份XML文件,生成对应目录结构的网站,不过只有html还是太过于简单了,如果要是可以连带生成css那就比较强大了.这个有待后续研发,先来研究下怎么html网站结构. 既然是通过XML结构生成网站,那所有的事情都应该由这个XML文件来.先来看下这个XML文件,website.xml: <website> <page name="index" title="Home page"> &l