Python数组中求和问题

作者:dyq666,zhihu.com/people/dyq666

本专题主要介绍哈希表和指针两种方法来解决该类问题,从两个数之和引申到三个数之和,再从四个数之和的问题上思考如何构建出一种通用的代码(可以解决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)

唯一需要注意的是同一个元素不能复用

nums_len = len(nums)

for i in range(0, nums_len):
    for j in range(i + 1, nums_len):
        if nums[i] + nums[j] == target:
            return [i, j]

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中存放的肯定是前一个值(因为是之前遍历过的)。

seen_dict = {} 

for i, num in enumerate(nums):

    search = target - num
    if search in seen_dict:
        return [seen_dict[search], i]
    else:
        seen_dict[num] = i

3. 双指针

(1) O(nlogn)-主要是快排的影响

(2) 在一个有序的数组中最左边一定是最小值,而最右边一定是最大值。我们可以将最小值与最大值相加与目标值进行比较,如果两数之和大于目标值,我们就让最大值小一点(也就是读取第二个最大值),相反如果小于,则让最小值大一点(读取第二个最小值)。这样我们就保证了一次循环就能查找到目标值,但数组必须是有序的。

回到题目中:

(1) 由于需要返回索引,所以我们必须存储两个数组,一个是无序的(用于查找真实的索引),另一个是有序的(用于查找符合题目的值)。

(2) 两个指针left和right分别指向数组中第一个元素和最后一个元素(最小值和最大值)

(3) 循环的结束条件为左指针大于等于右指针(左边的不能比右边的大,而且一个元素只能用一次)

(4) 然后就判断左值+右值与目标值之间的关系,在上面我们已经讨论过了大于和小于的情况。

(5) 当等于时由于我们需要得到左值和右值在原本数组的索引,我们需要考虑以下问题。从题目中的得知每个target只有一个答案, 意味着如果target是6不会出现[2, 2, 4]的情况, 但是会出现[3, 3]的情况, 也就是当两个相同的值满足情况是才会有重复的元素。所以我们先通过index获取左值对应的索引,如果左值和右值相同我们就获取下一个该值的索引,如果不同,我们直接获取右值相关的索引。

raw_nums = nums

nums = sorted(nums)

left, right = 0, len(nums) - 1   

while left < right:
    v_left, v_right = nums[left], nums[right]

    two_sum = v_left + v_right

    if two_sum > target:
        right -= 1
    elif two_sum < target:
        left += 1
    else:  # 找到了
        left_index = raw_nums.index(v_left)
        # 如果值相同就查找下一个该值的索引
        right_index = raw_nums.index(v_right, left + 1) if v_right == v_left else raw_nums.index(v_right)
        return [left_index, right_index]

总结

通过两个数求和问题初步了解数组求和问题,下一文将引申这两种方法在三个数求和中的应用。

原文发布于微信公众号 - Python中文社区(python-china)

原文发表时间:2018-08-04

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

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏C语言及其他语言

【优秀题解】题解 1178: 三进制小数

你的任务呢,是将一个有理数转换成三进制小数。“什么是三进制小数呢?”你一定会问,这很明白,就是以三为基(二进制数以2为基,而十进制数则以10为基)的小数。

12330
来自专栏mathor

小和问题

 在一个数组中,每一个数左边比当前数小的数累加起来,叫做这个数组的小和。求一个数组的小和。

26340
来自专栏ACM算法日常

HDU1106:排序 (重新修正)

之前发过一篇HDU 1106的题目,但是因为有童鞋说那篇的源码提交后超时,我们的AlphaWA童鞋重新做了一遍,这次是0ms!算是修正之前的问题,非常感谢~

9510
来自专栏用户画像

7.6.1 内部排序算法的比较

1、简单选择排序、直接插入排序和冒泡排序的平均情况下的时间复杂度都为O(n^2),并且实现过程比较简单,但直接插入排序和冒泡排序在最好的情况下时间复杂度可以达到...

7720
来自专栏云霄雨霁

字符串排序----三向字符串快速排序

25200
来自专栏python学习之旅

算法笔记(八):复杂度分析(二)

#感兴趣的可以去订阅极客时间前谷歌工程师的专栏:数据结构与算法之美,个人觉得写的很不错。这里只是我自己做的一个简单的笔记

16420
来自专栏糊一笑

排序算法总结与实现

写在前面 一直很惧怕算法,总是感觉特别伤脑子,因此至今为止,几种基本的排序算法一直都不是很清楚,更别说时间复杂度、空间复杂度什么的了。 今天抽空理了一下,其实感...

35390
来自专栏编程理解

排序算法(六):希尔排序

希尔排序是对插入排序的一种改进,也叫递减增量排序,算法过程中通过对增量值的递减调整,形成每一个增量值对应的一个或多个待排序分组,分别对分组执行插入排序,最后调整...

71210
来自专栏目标检测和深度学习

常用排序算法总结(1)

14220
来自专栏ACM算法日常

一次看懂进制转换(阶乘是关键) - HDU 2031

对于二进制的转换,我们通常有这样的公式,例如对于一个二进制111001,转换为十进制xx:

24030

扫码关注云+社区

领取腾讯云代金券