两个数、三个数、四个数的和

xiximayou 2019-10-04 原文

两个数、三个数、四个数的和

方法一:双指针法,先要对数组进行排序

a=[12,6,8,1,4,3]
def sum2(a,target):
    res=[]
    a=sorted(a)
    l,r=0,len(a)-1
    while l<r:
        tmp=[0,0]
        if a[l]+a[r]==target:
            tmp[0]=a[l]
            tmp[1]=a[r]
            res.append(tmp)
            l+=1
            r-=1
        elif a[l]+a[r]>target:
            r-=1
        else:
            l+=1
    return res
print(sum2(a,9))

输出:[[1, 8], [3, 6]]

方法二:对于第一种方法,主要时间都用在进行排序上,我们可以利用hash来避免进行排序。

def sum2(a,target):
    dic={}
    res=[]
    for i in range(len(a)):
        tmp=[0,0]
        m=a[i]
        if target-m in dic:
            tmp[0]=m
            tmp[1]=target-m
            res.append(tmp)
        dic[m]=i
    return res
print(sum2(a,10))

输出:[[1, 8], [3, 6]]

方法三:免去建立hash表

def sum2(a,target):
    res=[]
    for i in range(len(a)):
        tmp=[0,0]
        if  target-a[i] in a[i+1:]:
            tmp[0]=a[i]
            tmp[1]=target-a[i]
            res.append(tmp)
    return res
print(sum2(a,9))

输出:[[6, 3], [8, 1]]

扩展:方法三可以扩展到三个数的和、四个数的和等;

def sum3(a,target):
    res=[]
    for i in range(len(a)):
        for j in range(i+1,len(a)):
            tmp=[0,0,0]
            if target-a[i]-a[j] in a[j+1:]:
                tmp[0]=a[i]
                tmp[1]=a[j]
                tmp[2]=target-a[i]-a[j]
                res.append(tmp)
    return res
print(sum3(a,13))

输出:[[6, 4, 3], [8, 1, 4]]

def sum4(a,target):
    res=[]
    for i in range(len(a)):
        for j in range(i+1,len(a)):
            for k in range(j+1,len(a)):
                tmp=[0,0,0,0]
                if target-a[i]-a[j]-a[k] in a[k+1:]:
                    tmp[0]=a[i]
                    tmp[1]=a[j]
                    tmp[2]=a[k]
                    tmp[3]=target-a[i]-a[j]-a[k]
                    res.append(tmp)
    return res
print(sum4(a,24))

输出:[[12, 8, 1, 3]]

扩展:数组中的和为n,但不限个数,同时也不能重复

a=[12,6,8,1,4,3]
res=[]
def nor_sum(a,target,pos,end,tmp):
    global res
    if target<0:
        return
    if target==0:
        res.append(tmp[:])
    for i in range(pos,end):
        tmp.append(a[i])
        nor_sum(a,target-a[i],i+1,end,tmp)
        tmp.pop()
nor_sum(a,12,0,len(a),[])
print(res)

输出:[[12], [8, 1, 3], [8, 4]]

可以重复:(主要的区别如红色所标注的)

a=[12,6,8,4,3]
res=[]
def nor_sum(a,target,pos,end,tmp):
    global res
    if target<0:
        return
    if target==0:
        res.append(tmp[:])
    for i in range(pos,end):
        tmp.append(a[i])
        nor_sum(a,target-a[i],i,end,tmp)
        tmp.pop()
nor_sum(a,12,0,len(a),[])
print(res)

输出:[[12], [6, 6], [6, 3, 3], [8, 4], [4, 4, 4], [3, 3, 3, 3]]

 

发表于
2019-10-04 14:35 西西嘛呦 阅读() 评论() 编辑 收藏

 

版权声明:本文为xiximayou原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://www.cnblogs.com/xiximayou/p/11622102.html

两个数、三个数、四个数的和的更多相关文章

随机推荐

  1. 十、Spring boot 简单优雅的整合 Swagger2

    前言 swagger2 是什么,我这里就不说了,就是一个简单的接口文档,方便前后端联调。 其实之前没有想要到要 […]...

  2. bat批处理以当前时间创建文本文件

    :: 表示注释 :: @表示不显示当前命令,只在后台执行 :: @echo off 表示以后执行的命令都不显示 […]...

  3. 终于等到你!微软正式上线 Windows Terminal 预览版

    前一段时间,一直在知乎、技术社区收到技术小伙伴们的终极拷问:微软Build 大会上提到的**6月中旬**要上W […]...

  4. 提示源文件路径不存在

    1 提示源文件路径不存在,而实际上源文件路径是正确的   解决办法:网站站点的基本配置-》网站绑定-》将IP地 […]...

  5. 解决Tengine健康检查引起的TIME_WAIT堆积问题

    简介: 解决Tengine健康检查引起的TIME_WAIT堆积问题   一. 问题背景 “服务上云后,我们的T […]...

  6. ASP.NET Core 2.2 基础知识(四) URL重写中间件

    ASP.NET Core 2.2 基础知识(四) URL重写中间件 说到URL重写就不得不提URL重定向. U […]...

  7. 腾讯云申请SSL证书与Nginx配置Https

    0x00 为什么要安装证书 信息传输的保密性 数据交换的完整性 信息的不可否认性 交易者身份确定性 如今各大浏 […]...

  8. 微信支付结果通用通知

    支付结果通用通知 应用场景 支付完成后,微信会把相关支付结果和用户信息发送给商户,商户需要接收处理,并返回应答 […]...

展开目录

目录导航