方法一:双指针法,先要对数组进行排序
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
输出:[[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
输出:[[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]]