確定總和到數組中的某些值的整數對

-1

我有計算N個整數對的數目的總和爲value的程序數。爲了簡化問題，還假定整數是不同的。確定總和到數組中的某些值的整數對

l.Sort(); 
for (int i = 0; i < l.Count; ++i) 
{ 
    int j = l.BinarySearch(value - l[i]); 
    if (j > i) 
    { 
     Console.WriteLine("{0} {1}", i + 1, j+1); 
    } 
}

爲了解決這個問題，我們對數組進行排序（以啓用二進制搜索），然後，對陣列中的每個條目a[i]，爲value - a[i]做一個二進制搜索。如果結果是j與j > i索引，我們將顯示這一對。

但這種算法沒有在接下來的輸入工作：

1 2 3 4 4 9 56 90因爲j總是比i小。

如何解決這個問題？

來源

2015-11-07 Anatoly

在你的輸入中，你看到總和爲0的對嗎？ – Leeor

看起來他希望這兩個對的總和爲「value」，不一定是0. –

@TomZych是的，修正了它 – Anatoly

我會走更高效的解決方案，需要更多的空間。

假設數字並不明顯

與整數作爲一個鍵和一個頻率，在這個哈希表中的值
迭代創建一個哈希表。
對於每個鍵
- 計算差異diff = value - k
- 在散列
- 查找用於diff如果存在匹配檢查，如果該值已經得到頻率> 0
- 如果頻率是> 0遞減它由1個產量電流對k, diff

下面是一個Python代碼：

def count_pairs(arr, value): 
    hsh = {} 
    for k in arr: 
    cnt = hsh.get(k, 0) 
    hsh[k] = cnt + 1 
    for k in arr: 
    diff = value - k 
    cnt = hsh.get(diff) 
    if cnt > 0: 
     hsh[k] -= 1 
     print("Pair detected: " + str(k) + " and " + str(diff)) 

count_pairs([4, 2, 3, 4, 9, 1, 5, 4, 56, 90], 8) 
#=> Pair detected: 4 and 4 
#=> Pair detected: 3 and 5 
#=> Pair detected: 4 and 4 
#=> Pair detected: 4 and 4

至於counts the number of pairs是非常模糊的描述，在這裏你可以看到4個不同的（以數量的指標）對。

來源

2015-11-07 12:59:31 fl00r

如果您希望此爲非 -distinct值工作（這你問題不說，但您的評論暗示），二進制搜索僅i之後陣列的部分。這也消除了對測試的需要。

會顯示代碼，但我不知道如何在中指定您使用的任何語言的這種切片。

來源

2015-11-07 12:42:39

確定總和到數組中的某些值的整數對

回答

相關問題