Python数组中求和问题(python 数组加数组)
off999 2024-11-06 11:22 14 浏览 0 评论
优效学院,大数据,java,人工智能,架构,等在线教育
本专题主要介绍哈希表和指针两种方法来解决该类问题,从两个数之和引申到三个数之和,再从四个数之和的问题上思考如何构建出一种通用的代码(可以解决N个数之和)。本文主要内容是通过001问题来初步了解数组求和的两种常用方法。
001-Two Sum
给定一个整数数组和一个目标值,找出数组中和为目标值的两个数。 你可以假设每个输入只对应一种答案,且同样的元素不能被重复利用。
示例 :
给定 nums = [2, 7, 11, 15], target = 9
因为 nums[0] + nums[1] = 2 + 7 = 9 所以返回 [0, 1]
1. 暴力循环
O(n^2)
唯一需要注意的是同一个元素不能复用
2. 哈希
(1) O(n)
(2) 考虑暴力循环中我们做的事情,我们先挑出一个值a,然后看数组中其他值是否能与值a相加等于目标,也可以说成看数组中是否存在一个值等于目标值减去值a。
(3) 换个思路,我们将所有遍历过的值存放起来,每次遍历到一个新的值b时,我们可以查找目标值减去值b是否在我们存放的值中。基于哈希表的特性,查找的时间复杂度为O(1),总时间复杂度就变为了一次for循环O(n)
回到本道题中:
(1) 由于需要返回对应的索引,所以需要使用HashMap(在python中是dict),key存放数组中的值,value存放数组中的索引,遍历数组,将遍历过的值存入dict,如果目标值减去当前值在dict中则证明找到了目标值。
(2) 还有一点需要注意的是如果想按从小到大的顺序返回值,dict中存放的肯定是前一个值(因为是之前遍历过的)。
3. 双指针
(1) O(nlogn)-主要是快排的影响
(2) 在一个有序的数组中最左边一定是最小值,而最右边一定是最大值。我们可以将最小值与最大值相加与目标值进行比较,如果两数之和大于目标值,我们就让最大值小一点(也就是读取第二个最大值),相反如果小于,则让最小值大一点(读取第二个最小值)。这样我们就保证了一次循环就能查找到目标值,但数组必须是有序的。
回到题目中:
(1) 由于需要返回索引,所以我们必须存储两个数组,一个是无序的(用于查找真实的索引),另一个是有序的(用于查找符合题目的值)。
(2) 两个指针left和right分别指向数组中第一个元素和最后一个元素(最小值和最大值)
(3) 循环的结束条件为左指针大于等于右指针(左边的不能比右边的大,而且一个元素只能用一次)
(4) 然后就判断左值+右值与目标值之间的关系,在上面我们已经讨论过了大于和小于的情况。
(5) 当等于时由于我们需要得到左值和右值在原本数组的索引,我们需要考虑以下问题。从题目中的得知每个target只有一个答案, 意味着如果target是6不会出现[2, 2, 4]的情况, 但是会出现[3, 3]的情况, 也就是当两个相同的值满足情况是才会有重复的元素。所以我们先通过index获取左值对应的索引,如果左值和右值相同我们就获取下一个该值的索引,如果不同,我们直接获取右值相关的索引。
总结
通过两个数求和问题初步了解数组求和问题,下一文将引申这两种方法在三个数求和中的应用。
Python资料的私聊小编
相关推荐
- python入门到脱坑经典案例—清空列表
-
在Python中,清空列表是一个基础但重要的操作。clear()方法是最直接的方式,但还有其他方法也可以实现相同效果。以下是详细说明:1.使用clear()方法(Python3.3+推荐)...
- python中元组,列表,字典,集合删除项目方式的归纳
-
九三,君子终日乾乾,夕惕若,厉无咎。在使用python过程中会经常遇到这四种集合数据类型,今天就对这四种集合数据类型中删除项目的操作做个总结性的归纳。列表(List)是一种有序和可更改的集合。允许重复...
- Linux 下海量文件删除方法效率对比,最慢的竟然是 rm
-
Linux下海量文件删除方法效率对比,本次参赛选手一共6位,分别是:rm、find、findwithdelete、rsync、Python、Perl.首先建立50万个文件$testfor...
- 数据结构与算法——链式存储(链表)的插入及删除,
-
持续分享嵌入式技术,操作系统,算法,c语言/python等,欢迎小友关注支持上篇文章我们讲述了链表的基本概念及一些查找遍历的方法,本篇我们主要将一下链表的插入删除操作,以及采用堆栈方式如何创建链表。链...
- Python自动化:openpyxl写入数据,插入删除行列等基础操作
-
importopenpyxlwb=openpyxl.load_workbook("example1.xlsx")sh=wb['Sheet1']写入数据#...
- 在Linux下软件的安装与卸载(linux里的程序的安装与卸载命令)
-
通过apt安装/协助软件apt是AdvancedPackagingTool,是Linux下的一款安装包管理工具可以在终端中方便的安装/卸载/更新软件包命令使用格式:安装软件:sudoapt...
- Python 批量卸载关联包 pip-autoremove
-
pip工具在安装扩展包的时候会自动安装依赖的关联包,但是卸载时只删除单个包,无法卸载关联的包。pip-autoremove就是为了解决卸载关联包的问题。安装方法通过下面的命令安装:pipinsta...
- 用Python在Word文档中插入和删除文本框
-
在当今自动化办公需求日益增长的背景下,通过编程手段动态管理Word文档中的文本框元素已成为提升工作效率的关键技术路径。文本框作为文档排版中灵活的内容容器,既能承载多模态信息(如文字、图像),又可实现独...
- Python 从列表中删除值的多种实用方法详解
-
#Python从列表中删除值的多种实用方法详解在Python编程中,列表(List)是一种常用的数据结构,具有动态可变的特性。当我们需要从列表中删除元素时,根据不同的场景(如按值删除、按索引删除、...
- Python 中的前缀删除操作全指南(python删除前导0)
-
1.字符串前缀删除1.1使用内置方法Python提供了几种内置方法来处理字符串前缀的删除:#1.使用removeprefix()方法(Python3.9+)text="...
- 每天学点Python知识:如何删除空白
-
在Python中,删除空白可以分为几种不同的情况,常见的是针对字符串或列表中空白字符的处理。一、删除字符串中的空白1.删除字符串两端的空白(空格、\t、\n等)使用.strip()方法:s...
- Linux系统自带Python2&yum的卸载及重装
-
写在前面事情的起因是我昨天在测试Linux安装Python3的shell脚本时,需要卸载Python3重新安装一遍。但是通过如下命令卸载python3时,少写了个3,不小心将系统自带的python2也...
- 如何使用Python将多个excel文件数据快速汇总?
-
在数据分析和处理的过程中,Excel文件是我们经常会遇到的数据格式之一。本文将通过一个具体的示例,展示如何使用Python和Pandas库来读取、合并和处理多个Excel文件的数据,并最终生成一个包含...
- 【第三弹】用Python实现Excel的vlookup功能
-
今天继续用pandas实现Excel的vlookup功能,假设我们的2个表长成这样:我们希望把Sheet2的部门匹在Sheet1的最后一列。话不多说,先上代码:importpandasaspd...
- python中pandas读取excel单列及连续多列数据
-
案例:想获取test.xls中C列、H列以后(当H列后列数未知时)的所有数据。importpandasaspdfile_name=r'D:\test.xls'#表格绝对...
你 发表评论:
欢迎- 一周热门
- 最近发表
- 标签列表
-
- python计时 (73)
- python安装路径 (56)
- python类型转换 (93)
- python自定义函数 (53)
- python进度条 (67)
- python吧 (67)
- python字典遍历 (54)
- python的for循环 (65)
- python格式化字符串 (61)
- python串口编程 (60)
- python读取文件夹下所有文件 (59)
- java调用python脚本 (56)
- python操作mysql数据库 (66)
- python字典增加键值对 (53)
- python获取列表的长度 (64)
- python接口 (63)
- python调用函数 (57)
- python人脸识别 (54)
- python多态 (60)
- python命令行参数 (53)
- python匿名函数 (59)
- python打印九九乘法表 (65)
- python赋值 (62)
- python异常 (69)
- python元祖 (57)