k-sum问题

问题描述

1. 2-sum问题
   给定一个序列，计算出这个序列中两个数字相加等于0的个数
   假定给出的序列元素不包含0，且唯一
2. 3-sum问题
   同上，三个数相加等于0

解决方案

2-sum问题

算法第4版P119中提到
先进行排序，如果有这样的两个数字，一定是一个负数和一个正数，找出正数和负数的分界点，对负数集进行判断；用二分法查找负数的绝对值在给定的序列中是否存在，如果存在，则cnt加一，返回cnt；时间复杂度降到了O(nlgn),算法第4版中提到不存在比这时间复杂度更低的算法了

#前提条件是a序列中没有0元素
def two_sum(a):
    cnt=0
    a=sorted(a)#排序
    i=0
    while a[i]<0:
        i=i+1
    for j in a[:i]:
        #rank函数 如果查找成功，则返回其下标，否则返回-1,见文章底部
        if rank(-j,a,0,len(a)-1)>0:
            cnt=cnt+1
    return cnt

3-sum问题

算法第4版中给出的方法同2-sum问题，在最后一层进行二分查找，时间复杂度为O(n^2lgn)

def three_sum(a):
    cnt=0
    a=sorted(a)
    k=0
    while a[k]<0:
        k=k+1
    #第一个数只需要是负数即可，不用遍历正数
    for i in range(k):
        #第二个数要求在第一个数后，最后一个数之前
        for j in range(len(a)-1)[i+1:]:
            #将第二个数后的list传给rank函数
            if rank(-(a[i]+a[j]),a[j+1:],0,len(a[j+1:])-1)>=0:
                cnt=cnt+1
    return cnt

本文中提到的rank函数见 查找问题