讀完本文，你可以去力扣拿下如下題目：
1.兩數之和
170.兩數之和 III - 資料結構設計
-----------
Two Sum 系列問題在 LeetCode 上有好幾道，這篇文章就挑出有代表性的幾道，介紹一下這種問題怎麼解決。
TwoSum I這個問題的最基本形式是這樣：給你一個數組和一個整數 target，可以保證陣列中存在兩個數的和為 target，請你返回這兩個數的索引。
比如輸入 nums = [3,1,3,6], target = 6，演算法應該返回陣列 [0,2]，因為 3 + 3 = 6。
這個問題如何解決呢？首先最簡單粗暴的辦法當然是窮舉了：
int[] twoSum(int[] nums, int target) { for (int i = 0; i < nums.length; i++) for (int j = i + 1; j < nums.length; j++) if (nums[j] == target - nums[i]) return new int[] { i, j }; // 不存在這麼兩個數 return new int[] {-1, -1};}這個解法非常直接，時間複雜度 O(N^2)，空間複雜度 O(1)。
可以透過一個雜湊表減少時間複雜度：
int[] twoSum(int[] nums, int target) { int n = nums.length; index<Integer, Integer> index = new HashMap<>(); // 構造一個雜湊表：元素對映到相應的索引 for (int i = 0; i < n; i++) index.put(nums[i], i); for (int i = 0; i < n; i++) { int other = target - nums[i]; // 如果 other 存在且不是 nums[i] 本身 if (index.containsKey(other) && index.get(other) != i) return new int[] {i, index.get(other)}; } return new int[] {-1, -1};}這樣，由於雜湊表的查詢時間為 O(1)，演算法的時間複雜度降低到 O(N)，但是需要 O(N) 的空間複雜度來儲存雜湊表。不過綜合來看，是要比暴力解法高效的。
我覺得 Two Sum 系列問題就是想教我們如何使用雜湊表處理問題。我們接著往後看。
TwoSum II這裡我們稍微修改一下上面的問題。我們設計一個類，擁有兩個 API：
class TwoSum { // 向資料結構中新增一個數 number public void add(int number); // 尋找當前資料結構中是否存在兩個數的和為 value public boolean find(int value);}如何實現這兩個 API 呢，我們可以仿照上一道題目，使用一個雜湊表輔助 find 方法：
class TwoSum { Map<Integer, Integer> freq = new HashMap<>(); public void add(int number) { // 記錄 number 出現的次數 freq.put(number, freq.getOrDefault(number, 0) + 1); } public boolean find(int value) { for (Integer key : freq.keySet()) { int other = value - key; // 情況一 if (other == key && freq.get(key) > 1) return true; // 情況二 if (other != key && freq.containsKey(other)) return true; } return false; }}進行 find 的時候有兩種情況，舉個例子：
情況一：add 了 [3,3,2,5] 之後，執行 find(6)，由於 3 出現了兩次，3 + 3 = 6，所以返回 true。
情況二：add 了 [3,3,2,5] 之後，執行 find(7)，那麼 key 為 2，other 為 5 時演算法可以返回 true。
除了上述兩種情況外，find 只能返回 false 了。
對於這個解法的時間複雜度呢，add 方法是 O(1)，find 方法是 O(N)，空間複雜度為 O(N)，和上一道題目比較類似。
但是對於 API 的設計，是需要考慮現實情況的。比如說，我們設計的這個類，使用 find 方法非常頻繁，那麼每次都要 O(N) 的時間，豈不是很浪費費時間嗎？對於這種情況，我們是否可以做些最佳化呢？
是的，對於頻繁使用 find 方法的場景，我們可以進行最佳化。我們可以參考上一道題目的暴力解法，藉助雜湊集合來針對性最佳化 find 方法：
class TwoSum { Set<Integer> sum = new HashSet<>(); List<Integer> nums = new ArrayList<>(); public void add(int number) { // 記錄所有可能組成的和 for (int n : nums) sum.add(n + number); nums.add(number); } public boolean find(int value) { return sum.contains(value); }}這樣 sum 中就儲存了所有加入數字可能組成的和，每次 find 只要花費 O(1) 的時間在集合中判斷一下是否存在就行了，顯然非常適合頻繁使用 find 的場景。
三、總結對於 TwoSum 問題，一個難點就是給的陣列無序。對於一個無序的陣列，我們似乎什麼技巧也沒有，只能暴力窮舉所有可能。
一般情況下，我們會首先把陣列排序再考慮雙指標技巧。TwoSum 啟發我們，HashMap 或者 HashSet 也可以幫助我們處理無序陣列相關的簡單問題。
另外，設計的核心在於權衡，利用不同的資料結構，可以得到一些針對性的加強。
最後，如果 TwoSum I 中給的陣列是有序的，應該如何編寫演算法呢？答案很簡單，前文「雙指標技巧彙總」寫過：
int[] twoSum(int[] nums, int target) { int left = 0, right = nums.length - 1; while (left < right) { int sum = nums[left] + nums[right]; if (sum == target) { return new int[]{left, right}; } else if (sum < target) { left++; // 讓 sum 大一點 } else if (sum > target) { right--; // 讓 sum 小一點 } } // 不存在這樣兩個數 return new int[]{-1, -1};}