更好的算法（比使用字典）枚舉具有給定總和的對。

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 - 它將導致需要生成的元素的二次數。

但是 - 漸近地說 - 它不能做得更好，因爲它在輸入大小和輸出大小上是線性的。

Answer 2

非常非常簡單的解決方案，實際上通過使用數組引用在O（N）時間內運行。如果你想枚舉所有輸出對，那麼當然（作爲阿米特筆記），在最壞的情況下它必須佔用O（N^2）。

from collections import defaultdict 
def findpairs(arr, target): 
    flip = defaultdict(list) 
    for i, j in enumerate(arr): 
     flip[j].append(i) 
    for i, j in enumerate(arr): 
     if target-j in flip: 
      yield i, flip[target-j] 

後處理得到所有的輸出值（和濾除(i,i)答案）：

def allpairs(arr, target): 
    for i, js in findpairs(arr, target): 
     for j in js: 
      if i < j: yield (i, j) 

Answer 3

這可能會幫助 - Optimal Algorithm needed for finding pairs divisible by a given integer k

（有輕微的修改，還有我們看到的所有的對可以被給定的數字整除，不一定只是等於給定的數字）