Two Sum 系列問(wèn)題在 LeetCode 上有好幾道，這篇文章就挑出有代表性的兩道，介紹一下這種問(wèn)題怎么解決。

TwoSum I

這個(gè)問(wèn)題的最基本形式是這樣：給你一個(gè)數(shù)組和一個(gè)整數(shù)target，可以保證數(shù)組中存在兩個(gè)數(shù)的和為target，請(qǐng)你返回這兩個(gè)數(shù)的索引。

比如輸入nums = [3,1,3,6],target = 6，算法應(yīng)該返回?cái)?shù)組[0,2]，因?yàn)?3 + 3 = 6。

這個(gè)問(wèn)題如何解決呢？首先最簡(jiǎn)單粗暴的辦法當(dāng)然是窮舉了：

這個(gè)解法非常直接，時(shí)間復(fù)雜度 O(N^2)，空間復(fù)雜度 O(1)。

更好一點(diǎn)的解法，可以通過(guò)一個(gè)哈希表減少時(shí)間復(fù)雜度：

這樣，由于哈希表的查詢(xún)時(shí)間為 O(1)，算法的時(shí)間復(fù)雜度降低到 O(N)，但是需要 O(N) 的空間復(fù)雜度來(lái)存儲(chǔ)哈希表。不過(guò)綜合來(lái)看，是要比暴力解法高效的。

我覺(jué)得 Two Sum 系列問(wèn)題就是想教我們?nèi)绾问褂霉１硖幚韱?wèn)題。我們接著往后看。

TwoSum II

稍微修改一下上面的問(wèn)題，要求我們?cè)O(shè)計(jì)一個(gè)類(lèi)，擁有兩個(gè) API：

如何實(shí)現(xiàn)這兩個(gè) API 呢，我們可以仿照上一道題目，使用一個(gè)哈希表輔助find方法：

進(jìn)行find的時(shí)候有兩種情況，舉個(gè)例子：

情況一：如果連續(xù) add 了 [3,2,3,5]，那么freq是{3:2,2:1,5:1}，執(zhí)行find(6)，由于 3 出現(xiàn)了兩次，3 + 3 = 6，所以返回 true。

情況二：freq是{3:2,2:1,5:1}，執(zhí)行find(7)，那么key為 2，other為 5 時(shí)算法可以返回 true。

除了上述兩種情況外，find只能返回 false 了。

對(duì)于這個(gè)解法的時(shí)間復(fù)雜度呢，add方法是 O(1)，find方法是 O(N)，空間復(fù)雜度為 O(N)，和上一道題目比較類(lèi)似。

但是對(duì)于 API 的設(shè)計(jì)，是需要考慮現(xiàn)實(shí)情況的。比如說(shuō)，我們?cè)O(shè)計(jì)的這個(gè)類(lèi)，使用find方法非常頻繁，那么每次都要 O(N) 的時(shí)間，豈不是很浪費(fèi)費(fèi)時(shí)間嗎？對(duì)于這種情況，我們是否可以做些優(yōu)化呢？

是的，對(duì)于頻繁使用find方法的場(chǎng)景，我們可以進(jìn)行優(yōu)化。我們可以參考上一道題目的暴力解法，借助哈希集合來(lái)針對(duì)性?xún)?yōu)化find方法：

這樣sum中就儲(chǔ)存了所有加入數(shù)字可能組成的和，每次find只要花費(fèi) O(1) 的時(shí)間在集合中判斷一下是否存在就行了，顯然非常適合頻繁使用find的場(chǎng)景。

三、總結(jié)

對(duì)于 TwoSum 問(wèn)題，一個(gè)難點(diǎn)就是給的數(shù)組無(wú)序。對(duì)于一個(gè)無(wú)序的數(shù)組，我們似乎什么技巧也沒(méi)有，只能暴力窮舉所有可能。

一般情況下，我們會(huì)首先把數(shù)組排序再考慮雙指針技巧。TwoSum 啟發(fā)我們，HashMap 或者 HashSet 也可以幫助我們處理無(wú)序數(shù)組相關(guān)的簡(jiǎn)單問(wèn)題。

另外，設(shè)計(jì)的核心在于權(quán)衡，利用不同的數(shù)據(jù)結(jié)構(gòu)，可以得到一些針對(duì)性的加強(qiáng)。

最后，如果 TwoSum I 中給的數(shù)組是有序的，應(yīng)該如何編寫(xiě)算法呢？答案很簡(jiǎn)單，前文 雙指針技巧匯總 寫(xiě)過(guò)：

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 大一點(diǎn)
        } else if (sum > target) {
            right--; // 讓 sum 小一點(diǎn)
        }
    }
    // 不存在這樣兩個(gè)數(shù)
    return new int[]{-1, -1};