使用python重複條目求和K使用

我正在嘗試爲重複性面試問題做準備。給定一個數組，找到這些對以得到它們的總和爲k。我在這種情況下使用python字典而不是排序方法。代碼如下：使用python重複條目求和K使用

def sumToK(lst): 
    k = 16 # <- define the k here 
    d = {} # build a dictionary 

    # build the hashmap key = val of lst, value = i 
    for index, val in enumerate(lst): 
    d[val] = index 

# find the key; if a key is in the dict, and not the same index as the current key 
for i, val in enumerate(lst): 
    if (k-val) in d and d[k-val] != i: 
    print k-val, val 

a = [1,4,45,6,10,12,3] 
sumToK(a)

我正在以上述方式獲取重複值。我怎樣才能避免它？另外，如果數組包含重複的值，該怎麼辦？例如a = [1,4,45,6,10,12,4,8,8]謝謝。

來源

2015-09-10 deep

你在做太多的工作。你根本不需要跟蹤指數，你可以一次完成。只要保持你見過到目前爲止所有數字的set，併爲每個新號碼n你可以檢查其對（k - n）已經在你的設置：

def find_pairs(numbers, k): 
    seen = set() 
    for n in numbers: 
     if k - n in seen: 
      print n, k - n 
     seen.add(n) 

a = [1,4,45,6,10,12,3] 
find_pairs(a, 16) 
# 10 6 
# 12 4

如果你想防止重複對被打印，你可以改變條件，以確保n not in seen。

來源

2015-09-10 22:23:13 tzaman

您的發佈代碼中存在縮進錯誤。需要縮進開始「查找關鍵字」的註釋之後的for循環。

「重複值」我收集你的意思是，你得到的值都是4,12和值12,4。你可以通過讓你的測試要求第一個數小於第二個來消除這個例。

至於消除重複，使用一套而不是一個字典。你的代碼看起來過於複雜。

def sumTo(k, lst): 
    answer =set() 
    summands = set(lst) 
    for small in range(k/2): 
     large = k - small 
     if small in summands and large in summands: 
      answer.add((small, large)) 
    return answer

來源

2015-09-10 22:26:10 saulspatz

編輯：更改爲組合產品，以避免自組合

使用某些醇」時尚官能蟒。

from itertools import combination 
a = [1,4,45,6,10,12,4,8,8] 
k = 16 
set(
    map(
     lambda aa: tuple(sorted(aa)), 
     filter(
      lambda (a1, a2): a1+a2 == k, 
      combination(a, 2) 
     ) 
    ) 
) 

[Out]: set([(6, 10), (4, 12), (8, 8)])

來源

2015-09-10 22:31:56 sjosund

假設你只想要找到的值，而不是它們在列表中的位置/陣列

import itertools as it 
l = [1, 2, 3, 2, 3] 
k = 4 
s=[(a,b) for a,b in it.combinations(l,2) if a+b == k]

產生

[(1, 3), (1, 3), (2, 2)]

如果您想唯一對

set(s)

給出

set([(1, 3), (2, 2)])

來源

2015-09-10 22:42:53 Pynchia

使用python重複條目求和K使用

回答

相關問題