企业官网建设流程全解析

LeetCode 补拙笔记

0. 前言

• 日期：2026.09.03
• 题目：240.搜索二维矩阵 II
• 难度：中等
• 标签：数组 链表 哈希表

1. 题目理解

问题描述：
编写一个高效的算法来搜索 m x n 矩阵 matrix 中的一个目标值 target。该矩阵具有以下特性：
每行的元素从左到右升序排列。
每列的元素从上到下升序排列。

示例：

输入：matrix = [[1,4,7,11,15],[2,5,8,12,19],[3,6,9,16,22],[10,13,14,17,24],[18,21,23,26,30]], target = 5
输出：true

输入：matrix = [[1,4,7,11,15],[2,5,8,12,19],[3,6,9,16,22],[10,13,14,17,24],[18,21,23,26,30]], target = 20
输出：false

2. 解题思路

核心观察

矩阵行升序、列升序，选取矩阵右上角作为起始点。右上角元素，大于目标则目标不可能在当前列；小于目标则目标不可能在当前行；相等直接命中。不需要遍历全部矩阵，每次可以剔除一行或者一列。

算法步骤

1. 初始化指针x指向第一行，y指向最后一列。
2. 循环判定边界x不越行下边界，y不越列下边界。
3. 当前位置值大于target，y左移；小于target，x下移；等于target返回true。
4. 循环结束未找到，返回false。

3. 代码实现

packagelc240;publicclassSolution{publicbooleansearchMatrix(int[][]matrix,inttarget){intn=matrix.length-1;intx=0;inty=matrix[0].length-1;while(x<=n&&y>=0){if(matrix[x][y]>target){y--;}elseif(matrix[x][y]<target){x++;}else{returntrue;}}returnfalse;}}

4. 代码优化说明

{减少if分支判断，利用差值正负简化多分支条件，去掉else‑if，仅保留两个分支}

packagelc240;publicclassSolution{publicbooleansearchMatrix(int[][]matrix,inttarget){intn=matrix.length-1;intx=0;inty=matrix[0].length-1;while(x<=n&&y>=0){intdiff=matrix[x][y]-target;if(diff>0){y--;}elseif(diff<0){x++;}else{returntrue;}}returnfalse;}}

5. 复杂度分析

时间复杂度：O(m+n)，m为行数，n为列数。每轮循环x或者y发生移动，最多移动m+n次。
空间复杂度：O(1)，仅使用常数额外变量，无额外数组、集合开辟。

6. 总结

本题利用矩阵右上角特殊位置完成剪枝，不要使用暴力遍历O(m*n)，也不要每行单独二分O(m log n)。右上角游走是该题最优解法。优化版本将差值提前计算，减少数组重复访问，条件分支逻辑更加简洁。注意边界判断，防止数组下标越界。