兩個和與重複

Question

我一直在尋找兩個和問題：

鑑於整數數組，這兩個數字，使得他們增加了一個具體的目標回報指數。

並且對允許重複的變化感到困惑。爲什麼如果有重複，這是一個問題？我們不能只是返回重複的索引嗎？

Answer 1

爲了澄清他人，「重複變異」就是您所期望的：數字可以在數組中重複。

這並不重要，如果你寫一個蠻力算法。

但通常的非蠻力算法涉及將數字散列到它們的索引（，即創建反向數組）。以這種方式，給定目標T，人們檢查是否存在T - Array[0]作爲散列鍵（在這種情況下，解決方案已被找到），如果沒有，則繼續到T - Array[1]等等。

現在，如果所有數字都是唯一的，那麼上述方法就可以工作。如果號碼可以複製然而，有這樣的情況下，例如：

Array[] = {1, 3, 4, 4, 6, 8}; 
T = 8; 

散列必須包含一個一對多的映射4.因此，它涉及到確保你不小心產生了一加出來的相同的元素兩次，例如

Array[2] + Array[2]