Python面试:两数之和

如果你正在准备编程面试,那么你肯定会在某个面试时刻遇到两数之和的问题:

给定一个整数数组 nums 和一个目标值 target,请你在该数组中找出和为目标值的那 两个 整数,并返回他们的数组下标。你可以假设每种输入只会对应一个答案。但是,你不能重复利用这个数组中同样的元素。

示例:

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

因为 nums[0] + nums[1] = 2 + 7 = 9

所以返回 [0, 1]

尽管这是一个看似简单的问题,但是你可以采取多种方法,每种方法都有自己的优点和缺点。

方法一:基本方法

只需遍历所有可能的数字对,然后返回第一对,它们的总和就是你想要的。

这种方法在O(n²)时间和O(1)的空间中运行,其中n是arr的长度。

方法二:优化时间

第二种方法通过使用额外的空间来提高时间复杂度。

首先初始化一个空映射,它将用于存储之前的元素及其索引。

然后,对于列表中的每个元素,首先通过检查sum val-current是否在映射的键集中,来检查之前是否遇到过sum val-current。如果是,那么你已经找到了所需的对,因current_element + (sum_val - current_element) == sum_val 。

否则,将current_element添加到映射中,然后移动到下一个元素。

这种方法在O(n)时间和O(n)空间中运行。在这里,我们只访问每个数组元素一次,因为我们将以前看到的元素及其索引缓存在映射中。

方法三:优化空间

最后一种方法在不使用额外空间的情况下提高了时间复杂度,但是仍然比方法2使用更多的时间。

在这种方法中,我们首先对数组进行排序,并使用排序数组的属性来提高时间复杂度,而不需要使用辅助空间。

为此,我们将使用一个双指针方法。我们在第一个元素处开始一个指针,在最后一个元素处开始第二个指针。然后检查指针所指向的两个元素的和。

如果和太大,则递减第二个指针,如果和太小,则递增第一个指针。

因为数组是排序的,所以我们可以保证数组是不会减少。

这种方法在O(n*log(n))时间和O(1)空间中运行。这里我们假设使用的排序方法在O(n*log(n))时间和O(1)空间中运行,比如堆排序。

请注意,此方法的运行时中的主要因素来自排序操作。之后只进行O(n)比较,因为指针每次移动1,直到它们重叠为止。

在这里,我们改进了基本方法的时间复杂度,而不需要像方法2那样使用额外的存储。我们可以利用数组已排序的事实来最小化我们必须进行的比较的数量。

—End—

本文分享自微信公众号 - 量化投资与机器学习(Lhtz_Jqxx)

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2019-11-10

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏机器之心

获顶会最佳论文,天津大学等用强化学习寻找游戏bug

软件工程领域顶级会议 34th IEEE/ACM International Conference on Automated Software Engineer...

18010
来自专栏完美Excel

VBA实用小程序60: 替换图表SERIES公式中的字符串

大家知道,Excel图表的每个系列使用的数据都是由SERIES公式来确定的。当我们选取图表中的某个数据系列时,在公式栏中就会显示相应的SERIES公式,但这个公...

9520
来自专栏Java技术栈

如何写出让同事好维护的代码?

写出整洁的代码,是每个程序员的追求。《clean code》指出,要想写出好的代码,首先得知道什么是肮脏代码、什么是整洁代码;然后通过大量的刻意练习,才能真正写...

11720
来自专栏Crossin的编程教室

【Python 第75课】可迭代对象和迭代器

for 循环是我们在 Python 里非常常用的一个语法,但你有没有思考过 for 循环是怎样实现的?

10520
来自专栏码神路漫漫

如何实现 Go Module 依赖关系的可视化

最近,我开发了一个非常简单的小工具,总的代码量 200 行不到。今天,简单介绍下它。这是个什么工具呢?它是一个用于可视化展示 Go Module 依赖关系的工具...

13310
来自专栏业余草

面试再问ThreadLocal,别说你不会

以前面试的时候问到ThreadLocal总是一脸懵逼,只知道有这个哥们,不了解他是用来做什么的,更不清楚他的原理了。表面上看他是和多线程,线程同步有关的一个工具...

6910
来自专栏芋道源码1024

一个 Java 对象到底有多大?

编写Java代码的时候,大多数情况下,我们很少关注一个Java对象究竟有多大(占据多少内存),更多的是关注业务与逻辑。但是殊不知,在我们不经意间,大量的内存被无...

10410
来自专栏全栈前端精选

Redis 到底是怎么实现“附近的人”这个功能的呢?

针对“附近的人”这一位置服务领域的应用场景,常见的可使用PG、MySQL和MongoDB等多种DB的空间索引进行实现。而Redis另辟蹊径,结合其有序队列zse...

10910
来自专栏前端自习课

【JS】388- 深入了解强大的 ES6 「 ... 」 运算符

... 运算符,是 ES6 里一个新引入的运算法,也叫 展开/收集 运算符,我们每天都要和它打交道。

8020
来自专栏理想二旬不止

数据结构【第五篇】栈 (stack) 的实现与讲解

① 举一个生活中的例子:我在一个储物箱中,堆了一堆衣服,我的一件球衣在最下面,而我要拿这件衣服,就意味着我必须将上面的衣服全部拿出来才可以,但是由于箱子只有一个...

12030

扫码关注云+社区

领取腾讯云代金券

年度创作总结 领取年终奖励