面向大象程式設計
本期例題：LeetCode 167 - Two Sum II - Input array is sorted[1]（Easy）
給定一個已按照升序排列的有序數組，找到兩個數使得它們相加之和等于目标數（不可以重複使用同一個數），傳回兩個數的下标值 i 和 j，要求 i < j。
假設每個輸入有且僅有一個答案。
示例：
（注意：這裡和原題略有不同，下标改為從 0 開始，更自然。）
- 輸入： numbers = [2, 7, 11, 15]， target = 9
- 輸出： [0, 1]
Two Sum 是 LeetCode 的第一道題，你們應該都見過。乍一看來，Two Sum II 這道題和 Two Sum 問題一樣平平無奇。然而，這道題實際上内藏玄機，加上了數組有序的變化之後，它就換了一套解法。
如果你直接翻答案的話，會發現這就是一道普通的雙指針解法。兩個指針，
的時間。但是，如果你隻看答案，沒有了解背後的道理，就會陷入一看就會，一做就跪的困境。
實際上，在這個雙指針解法背後蘊含的是縮減搜尋空間的通用思想。那麼，這篇文章将會為你細細講述這個解法背後的道理，讓你能真正地了解這道經典題目。同時，要做到下次遇到同類題目時，可以快速想到這種解法。
這篇文章将會包含：
- 雙指針解法的正确性解釋
- 雙指針解法的背後原理：縮減搜尋空間
- 相同原理的另一道例題講解
- 相關題目
雙指針的解法
在做 Two Sum II 之前，你可能已經知道 Two Sum 的解法。使用一個散清單，做一次線性周遊，可以得到
時間複雜度、
空間複雜度的解法。那麼在 Two Sum II 中，數組有序這個變化，能幫助降低複雜度嗎？
看到有序這個條件，你可能首先想到的是二分查找。但是仔細一想，需要固定一個數，對另一個數進行二分查找，這樣時間複雜度是
，顯然不行。在不排序的情況下都做得到
時間、
空間。那麼我們的目标隻可能是：
的時間、
那麼怎麼能做到呢？這就是本題的雙指針解法了。讓我們先看看答案是怎麼寫的：
public int[] twoSum(int[] nums, int target) {
int i = 0;
int j = nums.length - 1;
while (i < j) {
int sum = nums[i] + nums[j];
if (sum < target) {
i++;
} else if (sum > target) {
j--;
} else {
return new int[]{i, j};
}
}
return new int[]{-1, -1};
} 代碼的邏輯很簡單，就輕輕巧巧地使用了兩個指針，一個隻向左移動，一個隻向右移動。走完一趟，就得到了答案。
兩個指針從兩頭向中間移動
兩個指針在中間相遇
很多題解都隻給出了這樣一個答案，仿佛道理是不證自明的。但事實上，這個解法并不是能讓人一眼就看懂。我第一次看到這道題的答案時，把這個解法叫做 Amazing O(n) 解法。這個解法的神奇之處在于，它把原本
的複雜度壓縮到了
，同時保證了算法的正确性。我們需要解釋它為什麼一定能得到解，而不會漏掉某些情況。
雙指針解法的正确性解釋
我們考慮兩個指針指向的數字，
A[i]
和
A[j]
。由于數組是有序的，在一開始，
A[i]
是數組中最小的數字，
A[j]
是最大的數字。我們将
A[i] + A[j]
與目标和
target
進行比較，則可能有兩種情況：
-
A[i] + A[j]
A[i]
A[i]
A[j]
A[j]
j
A[j]
-
A[i] + A[j]
A[j]
A[j]
A[i]
A[i]
i
A[i]
而第一步排除掉最左或最後的一個數後，我們再看子數組
A[i..j]
，其中
A[i]
又是最小的數字，
A[j]
又是最大的數字。我們可以繼續進行這樣的排除。以此類推，進行
可以看到，無論
A[i] + A[j]
的結果是大了還是小了，我們都可以排除掉其中一個數。這樣的排除法和二分搜尋很相似。二分搜尋通過每次排除一半的元素來減少比較的次數；而這道題的方法通過每次排除一個元素來減少比較的次數。兩者又恰好都是利用了數組有序這個性質。
說到這裡，這個解法的原理已經揭開一半了。接下來，我們再用更直覺的方式，從搜尋空間的角度真正地了解這道題。
搜尋空間的縮減過程
在這道題中，我們要尋找的是符合條件的一對下标
，它們需要滿足的限制條件是：
-
、
都是合法的下标，即
- （題目要求）
而我們希望從中找到滿足
A[i] + A[j] == target
的下标
。以
下标 i, j 的搜尋空間
由于
、
的限制條件的限制，搜尋空間是白色的倒三角部分。可以看到，搜尋空間的大小是
數量級的。如果用暴力解法求解，一次隻檢查一個單元格，那麼時間複雜度一定是
。而更優的算法，則可以在一次操作内排除掉多個不合格的單元格，進而快速削減搜尋空間，定位問題的解。
那麼我們來看看，本題的雙指針解法是如何削減搜尋空間的。一開始，我們檢查右上方單元格
，即計算
A[0] + A[7]
：
檢查單元格 0, 7
假設
A[0] + A[7]
小于目标和，由于
A[7]
已經是最大的數，我們可以推出
A[0] + A[6]
、
A[0] + A[5]
、……、
A[0] + A[1]
也都小于目标和，這些都是不合要求的解，可以一次排除，如下圖所示。這相當于排除
的全部解，削減了一行的搜尋空間，對應雙指針解法中的
i++
。
排除 i = 0 的全部解
在削減一行搜尋空間之後，剩餘的搜尋空間仍然是倒三角形狀。我們檢查右上方的單元格
：
檢查單元格 1, 7
假設
A[1] + A[7]
大于目标和，此時需要排除
的全部解，削減一列搜尋空間，對應雙指針解法中的
j--
：
排除 j = 7 的全部解
以此類推，每次會削減一行或一列的搜尋空間，經過
搜尋空間的減小過程（動圖）
舉一反三：二維矩陣搜尋
Two Sum II 或許太過簡單，并不需要用到搜尋空間的知識。那麼讓我們來看看這個思想在另一個例題中的應用。
例題：LeetCode 240 - Search a 2D Matrix II[2]（Medium）
一個寫一個高效的算法在矩陣中搜尋目标值 target。
- 每行的元素從左到右升序排列
- 每列的元素從上到下升序排列
這道題目的特點是，二維矩陣本身就是搜尋空間，是以我們不需要思考搜尋空間的形狀，直接進行搜尋即可。看到有序的這個條件，我們很容易想到使用二分搜尋。二分搜尋的中間點，顯然應該是矩陣的中心點：
二分搜尋的中間點
不過仔細思考就會發現，根據矩陣的性質，這個中心點把矩陣分成的四個部分中，隻有左上部分全部小于中心點，隻有右下部分全部大于中心點。也就是說做一次比較最多隻能削減 1/4 的搜尋空間。更大的問題是，删除掉左上部分或者右下部分之後，剩餘的形狀不再是一個規則的矩形，就無法繼續進行二分搜尋了。
一次比較最多删除 1/4 的搜尋空間
那麼我們不妨換一種思路，不追求一次削減一半的搜尋空間，而是像剛才的 Two Sum II 問題那樣，一次削減一行或者一列。類比剛才的雙指針解法，我們可以檢查矩陣右上角的元素，即
matrix[0][7]
。
檢查矩陣右上角的元素
如果
matrix[0][7]
小于目标值，由于矩陣每行是有序的，同一行所有的元素肯定都小于目标值，就可以排除一行的元素。
削減 i = 0 的一行搜尋空間
而如果
matrix[0][7]
大于目标值，由于矩陣每列是有序的，同一列所有的元素一定都大于目标值，這又可以排除一列的元素。
削減 j = 7 的一列搜尋空間
那麼，我們每次都必定可以排除一行或一列的元素。經過
總結
從本文的例題可以看出，LeetCode 很多題目的答案很簡單，但若想真正記住并舉一反三，還是要了解題目背後的思想。Two Sum II 表面上是一個簡單的雙指針解法，但為了能想出這個解法，需要了解背後的搜尋空間思想。
搜尋空間的技巧需要在實際題目中靈活運用，本文中二維矩陣搜尋例題的解法就是靈活運用了搜尋空間思想。這裡再列出一道和本題非常相關的題目，請仔細體會其中削減搜尋空間的思想：
- 11. Container With Most Water[3]
參考資料
[1]
LeetCode 167 - Two Sum II - Input array is sorted: https://leetcode.com/problems/two-sum-ii-input-array-is-sorted/
[2]
LeetCode 240 - Search a 2D Matrix II: https://leetcode.com/problems/search-a-2d-matrix-ii/
[3]
11. Container With Most Water: https://leetcode.com/problems/container-with-most-water/
歡迎關注我的公衆号“五分鐘學算法”，如果喜歡，麻煩點一下“