適用于有序矩陣(數(shù)組也是矩陣)，相比其他算法目的是減少搜索空間亲配，但是有前提條件尘应，有序。關(guān)鍵思想：固定參數(shù)吼虎，比較犬钢，舍棄不合適的搜索空間。
例子1思灰、給定一個(gè)已按照升序排列的有序數(shù)組玷犹，找到兩個(gè)數(shù)使得它們相加之和等于目標(biāo)數(shù)（不可以重復(fù)使用同一個(gè)數(shù)），返回兩個(gè)數(shù)的下標(biāo)值 i 和 j洒疚，要求 i < j歹颓。
假設(shè)每個(gè)輸入有且僅有一個(gè)答案坯屿。
示例：
輸入：numbers = [2, 7, 11, 15]， target = 9
輸出：[0, 1]
（注意：這里和原題略有不同巍扛，下標(biāo)改為從 0 開始领跛，更自然。）
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};
}
舉一反三：二維矩陣搜索
例題：LeetCode 240 - Search a 2D Matrix II[2]（Medium）
一個(gè)??的矩陣 matrix 有如下特點(diǎn)：
每行的元素從左到右升序排列
每列的元素從上到下升序排列
寫一個(gè)高效的算法在矩陣中搜索目標(biāo)值 target撤奸。
本期題解：LeetCode 11 - Container With Most Water[1]（Medium）
給定??個(gè)非負(fù)整數(shù)?吠昭，每個(gè)數(shù)代表坐標(biāo)中的一個(gè)點(diǎn)??。在坐標(biāo)內(nèi)畫??條豎直線寂呛，豎直線??的兩個(gè)端點(diǎn)分別為??和?怎诫。找出其中的兩條線瘾晃，使得它們與??軸共同構(gòu)成的容器可以容納最多的水贷痪。
說明：你不能傾斜容器，且??的值至少為 2蹦误。
題目示例
圖中垂直線代表輸入數(shù)組 [3,8,6,2,5,4,8,3,7]劫拢。在此情況下，容器能夠容納水（表示為藍(lán)色部分）的最大值為 49强胰。
public int maxArea(int[] height) {
? ? int res = 0;
? ? int i = 0;
? ? int j = height.length - 1;
? ? while (i < j) {
? ? ? ? int area = (j - i) * Math.min(height[i], height[j]);
? ? ? ? res = Math.max(res, area);
? ? ? ? if (height[i] < height[j]) {
? ? ? ? ? ? i++;
? ? ? ? } else {
? ? ? ? ? ? j--;
? ? ? ? }
? ? }
? ? return res;
}
