一文弄懂数组的和

发布时间：2020-12-20 09:51:11 所属栏目：Python 来源：网络整理

导读：方法一：双指针法，先要对数组进行排序 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:

方法一：双指针法，先要对数组进行排序

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来避免进行排序。

{}
    res=[]
    for i in range(len(a)):
        tmp=a[i]
        if target-m  dic:
            tmp[0]=m
            tmp[1]=target-m
            res.append(tmp)
        dic[m]=i
    
if  target-a[i]  a[i+1:]:
            tmp[0]=a[i]
            tmp[1]=target-a[i]
            res.append(tmp)
    
 sum3(a,1)"> range(len(a)):
        for j in range(i+1,len(a)):
            tmp=if target-a[i]-a[j]  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]]

 sum4(a,len(a)):
            for k in range(j+1if 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,3]]

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

a=[12,1)">]
res=[]
 nor_sum(a,target,pos,end,tmp):
    global res
    if target<0:
        return
    if target==0:
        res.append(tmp[:])
     range(pos,end):
        tmp.append(a[i])
        nor_sum(a,target-a[i],i+1print(res)

输出：[[12],4]]

可以重复：（主要的区别如红色所标注的）

a=[12,target-a[i],i,[6,6],3,4],[4,3]]
?
                        （编辑：李大同）
【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!