适用于有序矩阵(数组也是矩阵)，相比其他算法目的是减少搜索空间，但是有前提条件，有序。关键思想：固定参数，比较，舍弃不合适的搜索空间。
例子1、给定一个已按照升序排列的有序数组，找到两个数使得它们相加之和等于目标数（不可以重复使用同一个数），返回两个数的下标值 i 和 j，要求 i < j。
假设每个输入有且仅有一个答案。
示例：
输入：numbers = [2, 7, 11, 15]， target = 9
输出：[0, 1]
（注意：这里和原题略有不同，下标改为从 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）
一个 的矩阵 matrix 有如下特点：
每行的元素从左到右升序排列
每列的元素从上到下升序排列
写一个高效的算法在矩阵中搜索目标值 target。
本期题解：LeetCode 11 - Container With Most Water[1]（Medium）
给定 个非负整数 ，每个数代表坐标中的一个点 。在坐标内画 条竖直线，竖直线 的两个端点分别为 和 。找出其中的两条线，使得它们与 轴共同构成的容器可以容纳最多的水。
说明：你不能倾斜容器，且 的值至少为 2。
题目示例
图中垂直线代表输入数组 [3,8,6,2,5,4,8,3,7]。在此情况下，容器能够容纳水（表示为蓝色部分）的最大值为 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;
}
网友评论