更好的算法(比使用dict)枚举具有给定总和的对.

Question

给定一个数字,我必须找出给定数组中所有可能的索引对,其总和等于该数字.我目前正在使用以下算法:

def myfunc(array,num):
    dic = {}
    for x in xrange(len(array)):  # if 6 is the current key,
        if dic.has_key(num-array[x]):  #look at whether num-x is there in dic
            for y in dic[num-array[x]]: #if yes, print all key-pair values
                print (x,y),
        if dic.has_key(array[x]):  #check whether the current keyed value exists
            dic[array[x]].append(x)  #if so, append the index to the list of indexes for that keyed value
        else:
            dic[array[x]] = [x]  #else create a new array

这会O(N)及时运行吗？如果没有,那么应该做些什么呢？在任何情况下,是否可以在O(N)不使用任何辅助数据结构的情况下及时运行？

Answer 1

这会在O(N)时间内运行吗？

是的,不是.复杂性实际上是O(N + M)这里M是输出尺寸.
不幸的是,输出大小是O(N^2)最坏的情况,例如数组[3,3,3,3,3,...,3]和number == 6- 它将导致需要生成二次数的元素.

然而 - 渐近地说 - 它不能比这更好,因为它在输入大小和输出大小上是线性的.