02.2.1.4 二维矩阵与排序配合双指针
所属:全栈开发面试题库 / 02 数据结构与算法 / 02.2 数组、字符串与哈希 / 02.2.1 数组与双指针滑窗
02.2.1.4-001 二维矩阵在内存中怎么存?遍历顺序影响什么?
一句话结论
Java 二维数组是数组的数组,每行一个连续数组,行间引用跳转;按行遍历地址连续、缓存友好,按列遍历跨行跳转、缓存表现差。
概念解释
- 行优先:行内元素连续。
- 列遍历:每次跳到下一行同列。
- 局部性差异影响实测速度。
原理流程
- 确认行列规模。
- 热循环按行优先访问。
- 必须按列处理时评估缓存代价。
代码 / 示例
for (int i = 0; i < m; i++)
for (int j = 0; j < n; j++)
use(a[i][j]); // 行优先,连续
常见误区
- 误区:二维数组是一块连续大内存;正解:每行独立分配,行首是引用。
- 误区:行列遍历速度相同;正解:列遍历缓存失效率更高。
追问
- Q:矩阵转置复杂度? A:O(mn),逐个交换位置。
- Q:不规则矩阵(每行长度不同)? A:先取每行长度,不能假设 n 一致。
02.2.1.4-002 旋转图像(LC 48)原地怎么转 90 度?
一句话结论
先上下翻转(或主对角线转置),再沿另一对角线翻转;两步组合等价顺时针 90 度;原地 O(n²) 时间 O(1) 空间。
概念解释
- 转置:
a[i][j]与a[j][i]交换。 - 行反转:每行左右翻转。
- 组合得到顺时针旋转。
原理流程
- 主对角线转置。
- 每行水平反转。
- 核对四角映射。
代码 / 示例
public void rotate(int[][] a) {
int n = a.length;
for (int i = 0; i < n; i++)
for (int j = i + 1; j < n; j++) {
int t = a[i][j]; a[i][j] = a[j][i]; a[j][i] = t;
}
for (int[] row : a) reverse(row);
}
void reverse(int[] row) {
int l = 0, r = row.length - 1;
while (l < r) { int t = row[l]; row[l++] = row[r]; row[r--] = t; }
}
常见误区
- 误区:一步直接按映射写循环;正解:分步翻转更不易错,映射关系要核对。
- 误区:非方阵也套用;正解:题目为 n×n 方阵,矩形旋转需另开空间。
追问
- Q:逆时针 90 怎么改? A:反转顺序或改翻转方向。
- Q:不开原地怎么做? A:新矩阵
b[j][n-1-i]=a[i][j]。
02.2.1.4-003 螺旋矩阵(LC 54)怎么遍历?
一句话结论
维护上下左右四个边界,按右、下、左、上顺序逐层收缩;每走完一边收缩对应边界,并在每次移动前检查边界是否相交;O(mn) 时间。
概念解释
- 边界:top、bottom、left、right。
- 方向循环:右行 → 下列 → 左行 → 上列。
- 收缩后可能剩一行或一列,需检查边界。
原理流程
- 初始化四边界。
- 右行后 top++;下列后 right--。
- 左行前检查 top≤bottom;上行前检查 left≤right。
- 直到边界相交。
代码 / 示例
public List<Integer> spiralOrder(int[][] a) {
List<Integer> res = new ArrayList<>();
int t = 0, b = a.length - 1, l = 0, r = a[0].length - 1;
while (t <= b && l <= r) {
for (int j = l; j <= r; j++) res.add(a[t][j]);
t++;
for (int i = t; i <= b; i++) res.add(a[i][r]);
r--;
if (t <= b) for (int j = r; j >= l; j--) res.add(a[b][j]);
b--;
if (l <= r) for (int i = b; i >= t; i--) res.add(a[i][l]);
l++;
}
return res;
}
常见误区
- 误区:左行/上行前不检查边界;正解:可能只剩一行/一列,重复遍历。
- 误区:边界收缩顺序错位;正解:走完一边才收缩对应边界。
追问
- Q:单行矩阵输出什么? A:只走右行,其余方向被边界检查跳过。
- Q:螺旋遍历能用递归吗? A:可以按层递归,空间 O(min(m,n))。
02.2.1.4-004 螺旋矩阵 II(LC 59)怎么生成?
一句话结论
与遍历同构:四边界逐层向内,按顺序填入递增数字;O(n²) 时间 O(n²) 结果空间。
概念解释
- 填充顺序与遍历一致。
- 数字从 1 递增到 n²。
- 边界收缩规则相同。
原理流程
- 开 n×n 矩阵。
- 四边循环填数并收缩。
- 检查边界避免重复填。
代码 / 示例
public int[][] generateMatrix(int n) {
int[][] a = new int[n][n];
int t = 0, b = n - 1, l = 0, r = n - 1, num = 1;
while (t <= b && l <= r) {
for (int j = l; j <= r; j++) a[t][j] = num++;
t++;
for (int i = t; i <= b; i++) a[i][r] = num++;
r--;
if (t <= b) for (int j = r; j >= l; j--) a[b][j] = num++;
b--;
if (l <= r) for (int i = b; i >= t; i--) a[i][l] = num++;
l++;
}
return a;
}
常见误区
- 误区:数字填完边界不收缩;正解:每层填完必须收缩。
- 误区:奇数 n 中心格漏填;正解:最后一层单行/单列由边界检查覆盖。
追问
- Q:n=1? A:直接填中心格 1。
- Q:生成矩形 m×n? A:边界按 m、n 分别维护。
02.2.1.4-005 矩阵置零(LC 73)怎么做?
一句话结论
要求原地时用首行首列记录哪些行/列要置零,先记录再按标记清零;单独标记首行首列本身是否需要清零;O(mn) 时间 O(1) 额外空间。
概念解释
- 标记位:
a[i][0]记第 i 行,a[0][j]记第 j 列。 - 首行首列自身需额外布尔记录。
- 先标记后清零,避免标记被覆盖。
原理流程
- 记录首行、首列是否含零。
- 用内部格扫描,标记到首行首列。
- 按标记清内部行列。
- 最后处理首行首列。
代码 / 示例
public void setZeroes(int[][] a) {
int m = a.length, n = a[0].length;
boolean row0 = false, col0 = false;
for (int j = 0; j < n; j++) if (a[0][j] == 0) row0 = true;
for (int i = 0; i < m; i++) if (a[i][0] == 0) col0 = true;
for (int i = 1; i < m; i++)
for (int j = 1; j < n; j++)
if (a[i][j] == 0) { a[i][0] = 0; a[0][j] = 0; }
for (int i = 1; i < m; i++)
for (int j = 1; j < n; j++)
if (a[i][0] == 0 || a[0][j] == 0) a[i][j] = 0;
if (row0) for (int j = 0; j < n; j++) a[0][j] = 0;
if (col0) for (int i = 0; i < m; i++) a[i][0] = 0;
}
常见误区
- 误区:遇到零立刻清行清列;正解:会破坏后续扫描依据,必须先标记。
- 误区:首行首列标记位与自身混淆;正解:单独布尔记录。
追问
- Q:非原地做法? A:两个布尔数组记录行列,O(m+n) 空间。
- Q:标记位用 -1 可以吗? A:值域允许时可行,最后统一转零。
02.2.1.4-006 对角线遍历(LC 498)怎么控制方向?
一句话结论
按对角线编号遍历,方向在右上与左下之间切换;碰到边界换向并调整下一起点;O(mn) 时间 O(1) 额外空间。
概念解释
- 对角线:
i+j为定值。 - 方向:右上
i--, j++或左下i++, j--。 - 边界换向:触顶/触右/触底/触左。
原理流程
- 起点 (0,0),方向右上。
- 沿对角线走,出界时按边界调整起点。
- 切换方向继续。
代码 / 示例
public int[] findDiagonalOrder(int[][] a) {
int m = a.length, n = a[0].length;
int[] res = new int[m * n];
int i = 0, j = 0, up = 1;
for (int k = 0; k < res.length; k++) {
res[k] = a[i][j];
if (up == 1) {
if (j == n - 1) { i++; up = -1; }
else if (i == 0) { j++; up = -1; }
else { i--; j++; }
} else {
if (i == m - 1) { j++; up = 1; }
else if (j == 0) { i++; up = 1; }
else { i++; j--; }
}
}
return res;
}
常见误区
- 误区:边界换向顺序写反;正解:先判右边界再判上边界,避免越界。
- 误区:方向切换后起点错位;正解:按出界方向回退到合法起点。
追问
- Q:矩形不对称时? A:边界判断分别按 m、n 处理。
- Q:对角线求和类问题? A:按 i+j 或 i-j 分组。
02.2.1.4-007 搜索二维矩阵(LC 74)怎么二分?
一句话结论
矩阵每行有序且下一行首元素 ≥ 上一行尾元素,可视为拉长的一维有序数组;下标 mid 映射到 (mid/n, mid%n),二分 O(log(mn))。
概念解释
- 全局有序:行内有序 + 行间递增。
- 一维映射:折半下标换算行列。
- 前提:行间严格满足有序条件。
原理流程
- 低 0,高 m·n-1。
- mid 换算行列取值比较。
- 收缩二分区间。
代码 / 示例
public boolean searchMatrix(int[][] a, int t) {
int m = a.length, n = a[0].length;
int l = 0, r = m * n - 1;
while (l <= r) {
int mid = l + (r - l) / 2;
int v = a[mid / n][mid % n];
if (v == t) return true;
if (v < t) l = mid + 1; else r = mid - 1;
}
return false;
}
常见误区
- 误区:不满足行间有序也套一维二分;正解:LC 240 行列分别有序但全局无序,需另一策略。
- 误区:mid 映射行列写反;正解:行 = mid/n,列 = mid%n。
追问
- Q:两次二分做法? A:先二分定位行,再二分定位列,O(log m + log n)。
- Q:矩阵为空? A:入口判空返回 false。
02.2.1.4-008 有序矩阵查找(LC 240)为什么从右上角走?
一句话结论
行列分别有序但全局无序时,从右上角出发:当前值大则左移,小则下移;每步排除一行或一列,O(m+n) 时间 O(1) 空间。
概念解释
- 右上角:左小下大。
- 比较后方向唯一:大往左,小往下。
- 不重复排除行列。
原理流程
- 起点 (0, n-1)。
- 等于返回;大于目标左移;小于目标下移。
- 出界未命中返回 false。
代码 / 示例
public boolean searchMatrix(int[][] a, int t) {
int i = 0, j = a[0].length - 1;
while (i < a.length && j >= 0) {
if (a[i][j] == t) return true;
if (a[i][j] > t) j--; else i++;
}
return false;
}
常见误区
- 误区:从左上角开始;正解:左上角右大下也大,方向不唯一。
- 误区:套用一维二分;正解:全局无序,二分不成立。
追问
- Q:左下角对称策略? A:当前值大上移,小右移,同样 O(m+n)。
- Q:最坏走多少步? A:从一角到对角,m+n 步。
02.2.1.4-009 矩阵转置怎么写?
一句话结论
b[j][i] = a[i][j],m×n 转置为 n×m;非方阵必须新开结果矩阵;O(mn) 时间 O(mn) 结果空间。
概念解释
- 行列互换。
- 方阵可原地交换上三角。
- 非方阵尺寸变化,不能原地。
原理流程
- 按新尺寸开矩阵。
- 逐格映射。
- 核对行列下标。
代码 / 示例
public int[][] transpose(int[][] a) {
int m = a.length, n = a[0].length;
int[][] b = new int[n][m];
for (int i = 0; i < m; i++)
for (int j = 0; j < n; j++) b[j][i] = a[i][j];
return b;
}
常见误区
- 误区:非方阵原地转置;正解:尺寸不同必须新开。
- 误区:下标映射写反;正解:新行 = 旧列,新列 = 旧行。
追问
- Q:方阵原地转置? A:只遍历上三角交换
a[i][j]与a[j][i]。 - Q:转置与旋转关系? A:转置加行反转得到 90 度旋转。
02.2.1.4-010 三数之和(LC 15)怎么做?
一句话结论
排序后固定一个数 i,内层相向双指针找两数之和为 -a[i];命中后两侧跳过重复;时间 O(n²),空间 O(排序栈/结果)。
概念解释
- 排序使内层可双指针。
- 固定点枚举,内层夹逼。
- 去重在固定点与命中处。
原理流程
- 排序。
- i 枚举,跳过重复。
- l=i+1,r=n-1,按和移动。
- 命中记录并跳重复。
代码 / 示例
public List<List<Integer>> threeSum(int[] a) {
List<List<Integer>> res = new ArrayList<>();
Arrays.sort(a);
for (int i = 0; i < a.length - 2; i++) {
if (a[i] > 0) break;
if (i > 0 && a[i] == a[i - 1]) continue;
int l = i + 1, r = a.length - 1;
while (l < r) {
int s = a[i] + a[l] + a[r];
if (s == 0) {
res.add(Arrays.asList(a[i], a[l], a[r]));
while (l < r && a[l] == a[l + 1]) l++;
while (l < r && a[r] == a[r - 1]) r--;
l++; r--;
} else if (s < 0) l++; else r--;
}
}
return res;
}
常见误区
- 误区:固定点不跳重复;正解:相同 i 会产生重复三元组。
- 误区:命中后只移一侧;正解:两侧都要移动并跳重复。
追问
- Q:为什么
a[i] > 0可 break? A:排序后后续更大,三数之和不可能为 0。 - Q:哈希做法可行吗? A:可行但去重麻烦,排序双指针更直观。
02.2.1.4-011 最接近的三数之和(LC 16)怎么做?
一句话结论
排序 + 固定点 + 双指针,维护与 target 差值绝对值最小的组合;和偏小移 l,偏大移 r;O(n²) 时间。
概念解释
- 目标不是等于,而是差值最小。
- 每次比较更新最近答案。
- 命中差值 0 可直接返回。
原理流程
- 排序。
- 固定 i,双指针夹逼。
- 比较当前和与最近差值。
- 按和值移动指针。
代码 / 示例
public int threeSumClosest(int[] a, int target) {
Arrays.sort(a);
int best = a[0] + a[1] + a[2];
for (int i = 0; i < a.length - 2; i++) {
int l = i + 1, r = a.length - 1;
while (l < r) {
int sum = a[i] + a[l] + a[r];
if (Math.abs(sum - target) < Math.abs(best - target)) best = sum;
if (sum == target) return sum;
if (sum < target) l++; else r--;
}
}
return best;
}
常见误区
- 误区:记录差值符号而不是绝对值;正解:比较距离用绝对值。
- 误区:初始 best 未初始化;正解:取前三个元素作为初值。
追问
- Q:差值相同怎么选? A:按题目口径,通常保留先遇到的即可。
- Q:能剪枝吗? A:固定点段和明显偏离时可提前判断。
02.2.1.4-012 四数之和(LC 18)怎么扩展?
一句话结论
两层枚举固定两个数,内层双指针找另两个;外层跳过重复,必要时按范围剪枝;O(n³) 时间,去重逻辑与三数之和一致。
概念解释
- 外层 i、j 两层。
- 内层 l、r 双指针。
- 重复在每层枚举点跳过。
原理流程
- 排序。
- i、j 枚举并跳重复。
- 内层夹逼,命中跳重复。
- 越界范围剪枝。
代码 / 示例
public List<List<Integer>> fourSum(int[] a, int target) {
List<List<Integer>> res = new ArrayList<>();
Arrays.sort(a);
int n = a.length;
for (int i = 0; i < n - 3; i++) {
if (i > 0 && a[i] == a[i - 1]) continue;
for (int j = i + 1; j < n - 2; j++) {
if (j > i + 1 && a[j] == a[j - 1]) continue;
int l = j + 1, r = n - 1;
while (l < r) {
long sum = (long) a[i] + a[j] + a[l] + a[r];
if (sum == target) {
res.add(Arrays.asList(a[i], a[j], a[l], a[r]));
while (l < r && a[l] == a[l + 1]) l++;
while (l < r && a[r] == a[r - 1]) r--;
l++; r--;
} else if (sum < target) l++; else r--;
}
}
}
return res;
}
常见误区
- 误区:四数相加 int 溢出;正解:用 long 计算和再比较。
- 误区:只在最内层去重;正解:外层 i、j 都要跳重复。
追问
- Q:K 数之和通用思路? A:递归降维到两数之和,配合排序双指针。
- Q:剪枝怎么做? A:当前层最小/最大和与 target 比较,提前 break/continue。
02.2.1.4-013 三数之和的去重细节有哪些?
一句话结论
固定点与上一值相同则跳过;命中解后左右指针分别跳过相邻重复;排序是去重前提,保证重复值相邻。
概念解释
- 外层去重:避免相同首元素重复展开。
- 内层去重:避免相同第二、三元素重复收集。
- 顺序:先记录再跳重复。
原理流程
- 排序后重复相邻。
- 外层
a[i]==a[i-1]跳过。 - 命中后
while跳过相邻相等。
代码 / 图示
if (i > 0 && a[i] == a[i - 1]) continue;
while (l < r && a[l] == a[l + 1]) l++;
while (l < r && a[r] == a[r - 1]) r--;
常见误区
- 误区:用结果集合判重代替相邻跳过;正解:排序后相邻跳过更高效。
- 误区:跳重复时越界;正解:while 条件带 l<r。
追问
- Q:不排序怎么去重? A:把组合序列化入哈希集合判重。
- Q:重复元素参与计数吗? A:本题要不重复组合,跳过;计数题另算。
02.2.1.4-014 区间合并(LC 56)怎么做?
一句话结论
按区间左端点排序,遍历中当前区间与结果末段重叠则合并右端点,不重叠则新增;O(n log n) 排序 + O(n) 扫描。
概念解释
- 排序后区间按起点相邻。
- 重叠判断:当前起点 ≤ 末段终点。
- 合并取右端点较大值。
原理流程
- 按起点排序。
- 首段入结果。
- 逐段比较重叠,合并或追加。
代码 / 示例
public int[][] merge(int[][] intervals) {
Arrays.sort(intervals, (x, y) -> x[0] - y[0]);
List<int[]> res = new ArrayList<>();
for (int[] cur : intervals) {
if (res.isEmpty() || res.get(res.size() - 1)[1] < cur[0]) res.add(cur);
else res.get(res.size() - 1)[1] = Math.max(res.get(res.size() - 1)[1], cur[1]);
}
return res.toArray(new int[0][]);
}
常见误区
- 误区:按右端点排序;正解:按左端点排序才能顺序合并。
- 误区:重叠判断用严格小于;正解:端点相接(等于)也算合并。
追问
- Q:插入区间(LC 57)思路? A:先加左侧不重叠段,合并重叠段,再加右侧。
- Q:合并后区间有序吗? A:按起点升序。
02.2.1.4-015 排序配合双指针的通用前提是什么?
一句话结论
题目不要求保留原顺序,且内层匹配可由大小比较决定方向;排序预处理 O(n log n) 后,内层可双指针 O(n);需保留下标时不能直接排序。
概念解释
- 前提:可重排。
- 收益:内层枚举降为线性。
- 代价:排序时间与稳定性。
原理流程
- 确认输出不依赖原下标。
- 排序获得有序性。
- 外层枚举 + 内层双指针。
代码 / 图示
可排序:三数之和、区间合并
不可排序:要求返回原下标、相对顺序敏感
常见误区
- 误区:返回原下标还排序;正解:需保留下标映射。
- 误区:排序代价不计入;正解:整体复杂度含 O(n log n)。
追问
- Q:稳定排序有必要吗? A:仅当次级顺序敏感时关注稳定性。
- Q:排序后双指针为什么不回退? A:有序性使移动方向唯一。
02.2.1.4-016 矩阵遍历类问题的边界用例有哪些?
一句话结论
空矩阵、单行、单列、方阵、矩形不对称、单元素;验证边界收缩、换向与下标不越界。
概念解释
- 退化维度:行或列为 1。
- 不对称:m ≠ n。
- 空:入口判空。
原理流程
- 先判 null 与长度 0。
- 构造单行/单列用例。
- 走查边界变化。
代码 / 图示
[] / [[]] / 1×n / m×1 / n×n
矩形 m≠n
常见误区
- 误区:默认矩阵至少两行两列;正解:退化维度必须处理。
- 误区:访问 a[0][0] 前不判空;正解:先校验行与列存在。
追问
- Q:螺旋矩阵单行输出顺序? A:从左到右一行。
- Q:列遍历空列? A:列数为 0 时直接返回。
02.2.1.4-017 矩阵原地修改需要注意什么?
一句话结论
原地修改前确认题目允许覆盖;标记位方案要区分记录区与数据区;避免边扫描边清零破坏后续判断;必要时用布尔数组做非原地标记。
概念解释
- 可改性:题面是否允许改输入。
- 标记覆盖:记录位不能被中途清掉。
- 非原地备选:行列布尔数组。
原理流程
- 确认允许原地。
- 分离标记阶段与清零阶段。
- 边界行列单独记录。
代码 / 图示
阶段一:扫描记录标记
阶段二:按标记修改
不要在扫描中立即清零
常见误区
- 误区:标记与清零同一遍完成;正解:会把后续扫描依据清掉。
- 误区:原地方案影响其他调用方;正解:引用传递下原矩阵被改。
追问
- Q:标记位占用数据值怎么办? A:用额外布尔数组,或值域允许时用特殊标记。
- Q:旋转是原地吗? A:方阵可原地翻转组合;矩形需新开。
02.2.1.4-018 二维问题的复杂度怎么算?
一句话结论
矩阵规模 m×n,遍历一格 O(1),整体 O(mn);辅助空间按标记结构规模算;排序类按元素数 n 计 O(n log n)。
概念解释
- 时间:格数 × 单格代价。
- 空间:标记数组/结果矩阵。
- 行列规模分别标注。
原理流程
- 统计访问格数。
- 单格操作量级。
- 辅助结构规模。
代码 / 图示
遍历矩阵:O(mn)
标记位原地:O(1) 额外
布尔行列:O(m+n)
常见误区
- 误区:把 m、n 混为一个 n;正解:标注 O(mn),空间按 m/n 分别说。
- 误区:结果矩阵计入辅助空间;正解:输出空间按题面口径单列。
追问
- Q:二分查找矩阵复杂度? A:O(log(mn)),不是 O(m+n)。
- Q:右上角走路复杂度? A:O(m+n),每步排除一行或一列。
02.2.1.4-019 矩阵中哪些信息可以提前排序利用?
一句话结论
区间起止、元素配对、可脱离位置的统计量可排序;依赖行列位置、相邻关系、原下标的信息不能排序;排序前先判断输出是否要求保序。
概念解释
- 可排序:区间端点、数值配对。
- 不可排序:网格邻接、路径、原下标。
- 保序要求决定可行性。
原理流程
- 列出输出依赖的信息。
- 判断位置信息是否必须保留。
- 可排序则排序后双指针。
代码 / 图示
区间合并:端点可排序
路径/邻接:位置敏感,不可排序
原下标:需带下标一起排序
常见误区
- 误区:数值题一律先排序;正解:位置相关问题排序会破坏结构。
- 误区:排序后丢掉原下标;正解:需要时下标随元素一起携带。
追问
- Q:两数之和要求原下标? A:用哈希保留下标,不排序。
- Q:排序后如何回溯原位置? A:元素打包成 (值, 原下标) 再排序。
02.2.1.4-020 数组/矩阵题如何从暴力优化到双指针?
一句话结论
暴力枚举所有组合是 O(n²);若排序后大小关系能唯一决定指针移动方向,内层枚举降为线性扫描;先证明移动方向不会漏解,再落地双指针。
概念解释
- 暴力:枚举所有对/三元组。
- 有序性:比较即可排除一侧。
- 不漏解:移动方向由单调性保证。
原理流程
- 写暴力枚举基线。
- 观察有序后和值变化方向。
- 双指针单向收敛,计入排序代价。
代码 / 图示
暴力三数:O(n³)
排序 + 固定 + 双指针:O(n log n) + O(n²)
常见误区
- 误区:未证明不漏解就移指针;正解:先说明为何移动一侧不会错过答案。
- 误区:优化后忘记排序复杂度;正解:整体取高阶。
追问
- Q:什么情况双指针不能替代内层枚举? A:无序且不能排序、或匹配条件非大小比较。
- Q:双指针空间收益? A:O(1) 额外空间,对比内层哈希。