CS-Notes Leetcode 题解数组与矩阵类问题的 12 道经典题解与核心技巧精讲【免费下载链接】CS-Notes:books: 技术面试必备基础知识、Leetcode、计算机操作系统、计算机网络、系统设计项目地址: https://gitcode.com/GitHub_Trending/cs/CS-Notes本篇基于 CS-Notes 仓库中的 Leetcode 题解 - 数组与矩阵 整理系统讲解数组与矩阵这一数据结构在面试算法题中的 12 道经典题目涵盖双指针、二分查找、堆、原地交换定位、哈希计数等核心技巧并为每题给出完整 Java 实现、复杂度分析与适用边界。读完后你可以掌握值域为 [1, n] 的数组如何 O(1) 空间解环定位、有序矩阵中查找第 K 小元素的二分与堆两条技术路线等高频面试考点并能按题型快速匹配解法。文档定位与题目总览该文档是 Leetcode 题解 - 目录 中数据结构相关板块下数组与矩阵主题的实现与 链表、哈希表、字符串 等篇共同构成系列。系列 前言 说明其选題原则从 Leetcode 精选约 200 道题去除繁杂而缺乏算法思想的题目保留面试中经常被问到的经典题目并辅以 Weiss《数据结构与算法分析》 等参考资料。本篇收录的 12 道题目难度以 Easy 为主、Medium 为辅按原文档编号整理如下编号题目LeetCode 编号难度核心技巧1把数组中的 0 移到末尾283 Move ZeroesEasy双指针写指针2改变矩阵维度566 Reshape the MatrixEasy下标互化 index/n、index%n3找出数组中最长的连续 1485 Max Consecutive OnesEasy状态变量计数4有序矩阵查找240 Search a 2D Matrix IIMedium右上角出发线性扫描 O(mn)5有序矩阵的 Kth Element378 Kth Smallest Element in a Sorted MatrixMedium值域二分 / 小根堆6找出重复的数和丢失的数645 Set MismatchEasy原地交换归位7找出数组中重复的数287 Find the Duplicate NumberMedium值域二分 / 快慢指针找环入口8数组相邻差值的个数667 Beautiful Arrangement IIMedium构造法9数组的度697 Degree of an ArrayEasy哈希表记录频次与首末下标10对角元素相等的矩阵766 Toeplitz MatrixEasy对角线递归校验11嵌套数组565 Array NestingMedium原地标记访问求环长12分隔数组769 Max Chunks To Make SortedMedium前缀最大值判分块所有代码实现均为 Java以下逐题展开。1. 把数组中的 0 移到末尾283 Move Zeroes, Easy题目要求把数组中的 0 全部移到末尾其他元素保持相对顺序。原文档给出的示例为给定nums [0, 1, 0, 3, 12]处理后应为[1, 3, 12, 0, 0]。解法采用单趟写指针双指针思想用idx标记下一个非零元素应该写入的位置遍历中遇到非零元素就前移写入最后把剩余位置统一补 0public void moveZeroes(int[] nums) { int idx 0; for (int num : nums) { if (num ! 0) { nums[idx] num; } } while (idx nums.length) { nums[idx] 0; } }复杂度O(n) 时间、O(1) 空间一次遍历即可完成且非零元素的原相对顺序天然保持。这里的关键是读for-each 隐式指针与写idx分离写指针只前进不回退因此不会覆盖尚未处理的元素。这种写指针分离技巧在删除元素、去重等原地数组操作题中是通用模板。2. 改变矩阵维度566 Reshape the Matrix, Easy题目要求把 m 行 n 列的矩阵重塑为 r 行 c 列元素按行遍历顺序保持不变若m * n ! r * c则无法重塑返回原矩阵。原文档示例Input: nums [[1,2], [3,4]] r 1, c 4 Output: [[1,2,3,4]] Explanation: The row-traversing of nums is [1,2,3,4]. The new reshaped matrix is a 1 * 4 matrix, fill it row by row by using the previous list.解法核心是一维下标与二维下标的互化顺序填充第index个元素时它在新矩阵旧维度下的位置就是index / n行、index % n列public int[][] matrixReshape(int[][] nums, int r, int c) { int m nums.length, n nums[0].length; if (m * n ! r * c) { return nums; } int[][] reshapedNums new int[r][c]; int index 0; for (int i 0; i r; i) { for (int j 0; j c; j) { reshapedNums[i][j] nums[index / n][index % n]; index; } } return reshapedNums; }复杂度O(m·n) 时间、O(r·c) 空间。由于题目要求生成新矩阵而非原地修改空间无法避免index / n与index % n这对除法取商取余的下标换算公式是行优先存储矩阵的一维/二维互化基本式在矩阵转置、滑动窗口索引计算等场景反复出现。3. 找出数组中最长的连续 1485 Max Consecutive Ones, Easy题目要求统计数组中最长连续 1 的长度。解法只用两个状态变量cur记录以当前元素结尾的连续 1 长度max记录全局最大值遇到 0 则清零public int findMaxConsecutiveOnes(int[] nums) { int max 0, cur 0; for (int x : nums) { cur x 0 ? 0 : cur 1; max Math.max(max, cur); } return max; }复杂度O(n) 时间、O(1) 空间。这是局部状态 全局最优的单遍扫描范式与 Leetcode 题解 - 双指针 篇中滑动窗口类题目共享同一思想只维护与当前窗口相关的少量状态窗口非法时按规则收缩或重置。4. 有序矩阵查找240 Search a 2D Matrix II, Medium给定一个每行、每列都升序排列的矩阵查找目标值是否存在。原文档示例矩阵为[ [ 1, 5, 9], [10, 11, 13], [12, 13, 15] ]解法从右上角元素出发该位置是所在行最大、所在列最小的决策点——若目标更小则整列排除左移若目标更大则整行排除下移每步必能淘汰一行或一列public boolean searchMatrix(int[][] matrix, int target) { if (matrix null || matrix.length 0 || matrix[0].length 0) return false; int m matrix.length, n matrix[0].length; int row 0, col n - 1; while (row m col 0) { if (target matrix[row][col]) return true; else if (target matrix[row][col]) col--; else row; } return false; }复杂度O(m n) 时间、O(1) 空间起点只能选右上角或左下角左上角或右下角不具备一步排除一整行或一整列的性质。该解法与 二分查找 篇的基础折半查找不同这里矩阵只是行、列各自有序整体并非全序无法直接套用 O(logN) 的二分只能利用局部单调性做线性裁剪。5. 有序矩阵的 Kth Element378 Kth Smallest Element in a Sorted Matrix, Medium给定每行、每列均升序的矩阵求第 k 小的元素。原文档示例matrix [ [ 1, 5, 9], [10, 11, 13], [12, 13, 15] ], k 8, return 13.文档给出两条技术路线下面分别展开。路线一值域二分查找思路是在值域上做二分答案一定落在[matrix[0][0], matrix[m-1][n-1]]之间对候选值mid统计矩阵中不大于它的元素个数cnt若cnt k说明答案偏大否则偏小。利用每行有序对每行只需扫描到第一个大于mid的元素即可public int kthSmallest(int[][] matrix, int k) { int m matrix.length, n matrix[0].length; int lo matrix[0][0], hi matrix[m - 1][n - 1]; while (lo hi) { int mid lo (hi - lo) / 2; int cnt 0; for (int i 0; i m; i) { for (int j 0; j n matrix[i][j] mid; j) { cnt; } } if (cnt k) lo mid 1; else hi mid - 1; } return lo; }复杂度每轮统计 O(m·n)内层循环受行有序性约束提前退出二分轮数为 O(log(max − min))总计 O(m·n·log(max − min)) 时间、O(1) 空间。注意中值写法lo (hi - lo) / 2与 二分查找 篇强调的一致l h可能加法溢出而h - l不会应使用后者。路线二小根堆归并 k 路有序序列由于每行有序矩阵等价于 m 路升序序列的归并问题先把首行 n 个元素全部入堆每次弹出堆顶当前最小把同一列的下一行元素补入堆顶所在的下一位置弹出 k 次后堆顶即第 k 小public int kthSmallest(int[][] matrix, int k) { int m matrix.length, n matrix[0].length; PriorityQueueTuple pq new PriorityQueueTuple(); for(int j 0; j n; j) pq.offer(new Tuple(0, j, matrix[0][j])); for(int i 0; i k - 1; i) { // 小根堆去掉 k - 1 个堆顶元素此时堆顶元素就是第 k 的数 Tuple t pq.poll(); if(t.x m - 1) continue; pq.offer(new Tuple(t.x 1, t.y, matrix[t.x 1][t.y])); } return pq.poll().val; } class Tuple implements ComparableTuple { int x, y, val; public Tuple(int x, int y, int val) { this.x x; this.y y; this.val val; } Override public int compareTo(Tuple that) { return this.val - that.val; } }复杂度堆大小不超过 n弹出 k 次共 O(k·log n) 时间、O(n) 空间。compareTo按val比较即构成小根堆当弹出的行已是最后一行t.x m - 1时没有下一个同列元素可补入直接continue。两种路线的取舍值域二分空间更省O(1)实现更短堆解法在 k 远小于 m·n 时更优且天然复用仓库中 Java 容器 篇讲解的PriorityQueue用法。该题也可视为 剑指 Offer 40 题最小的 K 个数 中堆解法找 Top-K思路在二维有序结构上的推广。6. 找出重复的数和丢失的数645 Set Mismatch, Easy数组长度为 n本应包含 1 到 n 的所有整数但其中一个数被另一个数替换导致出现一个重复数和一个丢失数要求找出它们。原文档示例Input: nums [1,2,2,4] Output: [2,3]最直接的方法是先排序再扫描时间复杂度 O(N log N)。原文档指出本题可以 O(N) 时间、O(1) 空间求解主要思想是通过交换使数组元素归位把nums[i]交换到下标nums[i] - 1值为 x 的数应该位于下标 x − 1直到当前位置放对或目标位置已有相同值说明发现重复public int[] findErrorNums(int[] nums) { for (int i 0; i nums.length; i) { while (nums[i] ! i 1 nums[nums[i] - 1] ! nums[i]) { swap(nums, i, nums[i] - 1); } } for (int i 0; i nums.length; i) { if (nums[i] ! i 1) { return new int[]{nums[i], i 1}; } } return null; } private void swap(int[] nums, int i, int j) { int tmp nums[i]; nums[i] nums[j]; nums[j] tmp; }复杂度O(n) 平均时间每个位置最多被交换常数次while 循环总次数有界、O(1) 空间。归位后扫描时nums[i] ! i 1的下标 i 处nums[i]是重复数、i 1是丢失数。该值域为 [1, n] 时以下标定位值的技巧与 剑指 Offer 3 题数组中重复的数字、Leetcode 题解 - 排序 篇的计数/交换类思想同出一源。7. 找出数组中重复的数287 Find the Duplicate Number, Medium数组长度为 n 1所有数在 1 到 n 之间且只有一个数重复可能出现多次要求不能修改数组、不能使用额外空间。原文档给出两种解法。解法一值域二分对值域 [1, n] 二分统计值 ≤ mid 的元素个数cnt若cnt mid说明 [1, mid] 这个只有 mid 个值的区间里挤进了超过 mid 个元素必有重复答案在左半区否则在右半区public int findDuplicate(int[] nums) { int l 1, h nums.length - 1; while (l h) { int mid l (h - l) / 2; int cnt 0; for (int i 0; i nums.length; i) { if (nums[i] mid) cnt; } if (cnt mid) h mid - 1; else l mid 1; } return l; }复杂度O(n log n) 时间、O(1) 空间。解法二快慢指针找环入口把数组看作函数映射 f(i) nums[i]从下标 0 出发不断跳转由于值域为 [1, n]n 1 个下标必有两个下标映射到同一个值序列中必然形成环重复数就是环的入口。这与 Leetcode 题解 - 双指针 篇一个指针每次移动一个节点一个指针每次移动两个节点如果存在环这两个指针一定会相遇的快慢指针判环思想一致原文档也明确注释类似于有环链表中找出环的入口public int findDuplicate(int[] nums) { int slow nums[0], fast nums[nums[0]]; while (slow ! fast) { slow nums[slow]; fast nums[nums[fast]]; } fast 0; while (slow ! fast) { slow nums[slow]; fast nums[fast]; } return slow; }第一阶段让快慢指针相遇确认存在环第二阶段把一个指针重置到起点 0两指针同速前进相遇点即环入口重复数。复杂度O(n) 时间、O(1) 空间同时满足不改数组、不用额外空间的约束。这一数组即函数图、找环入口即找重复值的建模是本题最值得记住的结论。8. 数组相邻差值的个数667 Beautiful Arrangement II, Medium题目要求用 1 到 n 的整数构造一个数组使相邻元素差值绝对值的不同取值恰好为 k 个。原文档示例Input: n 3, k 2 Output: [1, 3, 2] Explanation: The [1, 3, 2] has three different positive integers ranging from 1 to 3, and the [2, 1] has exactly 2 distinct integers: 1 and 2.构造思路是让前 k 1 个元素交替取两端值形成序列1, k1, 2, k, 3, k-1, ...其相邻差值恰好是k, k-1, ..., 1共 k 个不同值剩余位置按k2, k3, ..., n顺序填充相邻差值全为 1已包含在前 k 个差值中不引入新差值public int[] constructArray(int n, int k) { int[] ret new int[n]; ret[0] 1; for (int i 1, interval k; i k; i, interval--) { ret[i] i % 2 1 ? ret[i - 1] interval : ret[i - 1] - interval; } for (int i k 1; i n; i) { ret[i] i 1; } return ret; }复杂度O(n) 时间、O(1) 额外空间。interval从 k 递减奇数步加、偶数步减即可在 O(1) 内递推出生成前 k1 个摆动元素该构造法属于 Leetcode 题解 - 贪心思想 与构造类题目中先满足最难约束再退化填充的典型套路。9. 数组的度697 Degree of an Array, Easy数组的度定义为元素出现的最高频率例如[1,2,2,3,1,4,2]中 2 出现 3 次度为 3。题目要求找到与原数组度相同的最小长度子数组。原文档示例输入[1,2,2,3,1,4,2]输出6。解法用三个哈希表分别记录每个元素的出现次数、最后出现下标、首次出现下标满足度不变的子数组必须完整覆盖某个最高频元素的首末次出现区间答案即这些区间长度的最小值public int findShortestSubArray(int[] nums) { MapInteger, Integer numsCnt new HashMap(); MapInteger, Integer numsLastIndex new HashMap(); MapInteger, Integer numsFirstIndex new HashMap(); for (int i 0; i nums.length; i) { int num nums[i]; numsCnt.put(num, numsCnt.getOrDefault(num, 0) 1); numsLastIndex.put(num, i); if (!numsFirstIndex.containsKey(num)) { numsFirstIndex.put(num, i); } } int maxCnt 0; for (int num : nums) { maxCnt Math.max(maxCnt, numsCnt.get(num)); } int ret nums.length; for (int i 0; i nums.length; i) { int num nums[i]; int cnt numsCnt.get(num); if (cnt ! maxCnt) continue; ret Math.min(ret, numsLastIndex.get(num) - numsFirstIndex.get(num) 1); } return ret; }复杂度O(n) 时间、O(n) 空间哈希表规模等于元素种类数。核心结论是最小窗口一定由某个最高频元素的首末次出现撑开这与 Leetcode 题解 - 哈希表 篇中用哈希表把 O(n) 扫描的信息一次性聚合再按条件过滤的模式一致。10. 对角元素相等的矩阵766 Toeplitz Matrix, Easy托普利茨矩阵要求每条从左上到右下走向的对角线上所有元素相等。原文档示例1234 5123 9512 In the above grid, the diagonals are [9], [5, 5], [1, 1, 1], [2, 2, 2], [3, 3], [4], and in each diagonal all elements are the same, so the answer is True.每条对角线必然以第一行某个元素或第一列某个元素为起点因此只需从这两组起点出发、沿 (row1, col1) 方向递归校验整条对角线是否与起点值一致public boolean isToeplitzMatrix(int[][] matrix) { for (int i 0; i matrix[0].length; i) { if (!check(matrix, matrix[0][i], 0, i)) { return false; } } for (int i 0; i matrix.length; i) { if (!check(matrix, matrix[i][0], i, 0)) { return false; } } return true; } private boolean check(int[][] matrix, int expectValue, int row, int col) { if (row matrix.length || col matrix[0].length) { return true; } if (matrix[row][col] ! expectValue) { return false; } return check(matrix, expectValue, row 1, col 1); }复杂度O(m·n) 时间、O(min(m, n)) 栈空间递归深度为对角线长度。递归写法清晰表达沿对角线方向推进等价于迭代版本while (row m col n) { ...; row; col; }若不想占用调用栈可按 Java 虚拟机 篇对栈帧结构的理解自行改为迭代避免深矩阵下的递归深度问题。11. 嵌套数组565 Array Nesting, Medium给定元素为 0 到 n−1 的一个排列 A对每个下标 i 定义序列 S[i] {A[i], A[A[i]], A[A[A[i]]], ...}下标不断作为值再查表直到即将重复为止求所有 S[i] 的最大长度。原文档示例Input: A [5,4,0,3,1,6,2] Output: 4 Explanation: A[0] 5, A[1] 4, A[2] 0, A[3] 3, A[4] 1, A[5] 6, A[6] 2. One of the longest S[K]: S[0] {A[0], A[5], A[6], A[2]} {5, 6, 2, 0}从源码结构看解法把数组本身当作访问标记表沿 S[i] 前进时把经过的下标置为 −1下次外层循环遇到 −1 即停止内层推进从而每个下标只被访问一次总复杂度 O(n)public int arrayNesting(int[] nums) { int max 0; for (int i 0; i nums.length; i) { int cnt 0; for (int j i; nums[j] ! -1; ) { cnt; int t nums[j]; nums[j] -1; // 标记该位置已经被访问 j t; } max Math.max(max, cnt); } return max; }复杂度O(n) 时间、O(1) 额外空间但注意该实现会破坏输入数组原地标记 −1若题目要求不能修改数组可改用boolean[]访问标记以 O(n) 空间换取非破坏性。本质上 A 是一个 0~n−1 上的置换S[i] 就是 i 所在置换环的长度本题即求置换的最长环——与第 7 题的数组即函数图建模互为镜像。12. 分隔数组769 Max Chunks To Make Sorted, Medium给定 0 到 n−1 的一个排列允许把它划分成若干连续子块每块独立排序后拼接仍等于原排序数组求最多能划分多少块。原文档示例Input: arr [1,0,2,3,4] Output: 4 Explanation: We can split into two chunks, such as [1, 0], [2, 3, 4]. However, splitting into [1, 0], [2], [3], [4] is the highest number of chunks possible.判据是前缀最大值恰好等于当前下标记扫描到 i 为止的前缀最大值为right若right i说明前缀中所有 ≤ i 的数都已齐备因为排列中值域恰好是 0..n−1前缀内部怎么排序都会落在 [0, i] 区间内不会与后部交叉可以在 i 处切一刀public int maxChunksToSorted(int[] arr) { if (arr null) return 0; int ret 0; int right arr[0]; for (int i 0; i arr.length; i) { right Math.max(right, arr[i]); if (right i) ret; } return ret; }复杂度O(n) 时间、O(1) 空间。该题是 Leetcode 题解 - 双指针 类前缀聚合 条件切分的代表right就是前缀聚合状态right i就是切分条件若把数组换成含重复值的通用数组则需扩展为前缀最大值等于前缀内排序最大值的比较版本。技巧总结与延伸索引回顾 12 道题可归纳出数组与矩阵题型的几条主线写指针 / 双指针第 1、3 题读写分离或局部状态单遍扫描O(n) 时间 O(1) 空间的原地操作模板下标与值域的互化第 2、6 题index/n、index%n的矩阵一维化以及值在 [1, n] 时以下标定位值的原地归位利用单调性裁剪搜索空间第 4、5 题有序矩阵的右上角线性扫描、值域二分加计数、k 路归并小根堆三条路线可按 k 的大小与空间要求权衡快慢指针 / 环检测第 7 题把数组建成函数映射图Floyd 判环找入口是禁改数组 禁额外空间约束下的标准解哈希聚合第 9 题一次扫描聚合频次与位置信息二次扫描取最优原地标记第 11 题把输入数组本身当访问表置换环长统计前缀聚合判切分点第 12 题前缀最大值与下标相等即为合法切分。这些技巧在仓库的其他题解篇中有对应展开可按需延伸阅读Leetcode 题解 - 目录系列全部 200 题的分类导航与参考资料Leetcode 题解 - 双指针快慢指针判环、对撞指针等第 3、7 题相关技巧的更多题目Leetcode 题解 - 二分查找中值防溢出写法、查找区间等二分变体第 5、7 题二分解法的底层依据Leetcode 题解 - 哈希表第 9 题哈希聚合模式的更多应用Leetcode 题解 - 排序与交换归位、前缀判据相关的排序思想剑指 Offer 3 题数组中重复的数字 与 剑指 Offer 40 题最小的 K 个数值域定位与 Top-K 堆解法的姊妹题。需要说明的适用前提本文全部代码沿用原文档的 Java 实现JDK 1.8 的增强 for 循环、PriorityQueue等标准 API 即可运行第 11 题解法会原地修改输入数组实际使用时注意这一副作用各题复杂度分析基于 LeetCode 原题的输入约束如第 6、7 题的值域 [1, n] 前提若输入约束变化解法适用性需重新评估。【免费下载链接】CS-Notes:books: 技术面试必备基础知识、Leetcode、计算机操作系统、计算机网络、系统设计项目地址: https://gitcode.com/GitHub_Trending/cs/CS-Notes创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考
CS-Notes Leetcode 题解：数组与矩阵类问题的 12 道经典题解与核心技巧精讲
CS-Notes Leetcode 题解数组与矩阵类问题的 12 道经典题解与核心技巧精讲【免费下载链接】CS-Notes:books: 技术面试必备基础知识、Leetcode、计算机操作系统、计算机网络、系统设计项目地址: https://gitcode.com/GitHub_Trending/cs/CS-Notes本篇基于 CS-Notes 仓库中的 Leetcode 题解 - 数组与矩阵 整理系统讲解数组与矩阵这一数据结构在面试算法题中的 12 道经典题目涵盖双指针、二分查找、堆、原地交换定位、哈希计数等核心技巧并为每题给出完整 Java 实现、复杂度分析与适用边界。读完后你可以掌握值域为 [1, n] 的数组如何 O(1) 空间解环定位、有序矩阵中查找第 K 小元素的二分与堆两条技术路线等高频面试考点并能按题型快速匹配解法。文档定位与题目总览该文档是 Leetcode 题解 - 目录 中数据结构相关板块下数组与矩阵主题的实现与 链表、哈希表、字符串 等篇共同构成系列。系列 前言 说明其选題原则从 Leetcode 精选约 200 道题去除繁杂而缺乏算法思想的题目保留面试中经常被问到的经典题目并辅以 Weiss《数据结构与算法分析》 等参考资料。本篇收录的 12 道题目难度以 Easy 为主、Medium 为辅按原文档编号整理如下编号题目LeetCode 编号难度核心技巧1把数组中的 0 移到末尾283 Move ZeroesEasy双指针写指针2改变矩阵维度566 Reshape the MatrixEasy下标互化 index/n、index%n3找出数组中最长的连续 1485 Max Consecutive OnesEasy状态变量计数4有序矩阵查找240 Search a 2D Matrix IIMedium右上角出发线性扫描 O(mn)5有序矩阵的 Kth Element378 Kth Smallest Element in a Sorted MatrixMedium值域二分 / 小根堆6找出重复的数和丢失的数645 Set MismatchEasy原地交换归位7找出数组中重复的数287 Find the Duplicate NumberMedium值域二分 / 快慢指针找环入口8数组相邻差值的个数667 Beautiful Arrangement IIMedium构造法9数组的度697 Degree of an ArrayEasy哈希表记录频次与首末下标10对角元素相等的矩阵766 Toeplitz MatrixEasy对角线递归校验11嵌套数组565 Array NestingMedium原地标记访问求环长12分隔数组769 Max Chunks To Make SortedMedium前缀最大值判分块所有代码实现均为 Java以下逐题展开。1. 把数组中的 0 移到末尾283 Move Zeroes, Easy题目要求把数组中的 0 全部移到末尾其他元素保持相对顺序。原文档给出的示例为给定nums [0, 1, 0, 3, 12]处理后应为[1, 3, 12, 0, 0]。解法采用单趟写指针双指针思想用idx标记下一个非零元素应该写入的位置遍历中遇到非零元素就前移写入最后把剩余位置统一补 0public void moveZeroes(int[] nums) { int idx 0; for (int num : nums) { if (num ! 0) { nums[idx] num; } } while (idx nums.length) { nums[idx] 0; } }复杂度O(n) 时间、O(1) 空间一次遍历即可完成且非零元素的原相对顺序天然保持。这里的关键是读for-each 隐式指针与写idx分离写指针只前进不回退因此不会覆盖尚未处理的元素。这种写指针分离技巧在删除元素、去重等原地数组操作题中是通用模板。2. 改变矩阵维度566 Reshape the Matrix, Easy题目要求把 m 行 n 列的矩阵重塑为 r 行 c 列元素按行遍历顺序保持不变若m * n ! r * c则无法重塑返回原矩阵。原文档示例Input: nums [[1,2], [3,4]] r 1, c 4 Output: [[1,2,3,4]] Explanation: The row-traversing of nums is [1,2,3,4]. The new reshaped matrix is a 1 * 4 matrix, fill it row by row by using the previous list.解法核心是一维下标与二维下标的互化顺序填充第index个元素时它在新矩阵旧维度下的位置就是index / n行、index % n列public int[][] matrixReshape(int[][] nums, int r, int c) { int m nums.length, n nums[0].length; if (m * n ! r * c) { return nums; } int[][] reshapedNums new int[r][c]; int index 0; for (int i 0; i r; i) { for (int j 0; j c; j) { reshapedNums[i][j] nums[index / n][index % n]; index; } } return reshapedNums; }复杂度O(m·n) 时间、O(r·c) 空间。由于题目要求生成新矩阵而非原地修改空间无法避免index / n与index % n这对除法取商取余的下标换算公式是行优先存储矩阵的一维/二维互化基本式在矩阵转置、滑动窗口索引计算等场景反复出现。3. 找出数组中最长的连续 1485 Max Consecutive Ones, Easy题目要求统计数组中最长连续 1 的长度。解法只用两个状态变量cur记录以当前元素结尾的连续 1 长度max记录全局最大值遇到 0 则清零public int findMaxConsecutiveOnes(int[] nums) { int max 0, cur 0; for (int x : nums) { cur x 0 ? 0 : cur 1; max Math.max(max, cur); } return max; }复杂度O(n) 时间、O(1) 空间。这是局部状态 全局最优的单遍扫描范式与 Leetcode 题解 - 双指针 篇中滑动窗口类题目共享同一思想只维护与当前窗口相关的少量状态窗口非法时按规则收缩或重置。4. 有序矩阵查找240 Search a 2D Matrix II, Medium给定一个每行、每列都升序排列的矩阵查找目标值是否存在。原文档示例矩阵为[ [ 1, 5, 9], [10, 11, 13], [12, 13, 15] ]解法从右上角元素出发该位置是所在行最大、所在列最小的决策点——若目标更小则整列排除左移若目标更大则整行排除下移每步必能淘汰一行或一列public boolean searchMatrix(int[][] matrix, int target) { if (matrix null || matrix.length 0 || matrix[0].length 0) return false; int m matrix.length, n matrix[0].length; int row 0, col n - 1; while (row m col 0) { if (target matrix[row][col]) return true; else if (target matrix[row][col]) col--; else row; } return false; }复杂度O(m n) 时间、O(1) 空间起点只能选右上角或左下角左上角或右下角不具备一步排除一整行或一整列的性质。该解法与 二分查找 篇的基础折半查找不同这里矩阵只是行、列各自有序整体并非全序无法直接套用 O(logN) 的二分只能利用局部单调性做线性裁剪。5. 有序矩阵的 Kth Element378 Kth Smallest Element in a Sorted Matrix, Medium给定每行、每列均升序的矩阵求第 k 小的元素。原文档示例matrix [ [ 1, 5, 9], [10, 11, 13], [12, 13, 15] ], k 8, return 13.文档给出两条技术路线下面分别展开。路线一值域二分查找思路是在值域上做二分答案一定落在[matrix[0][0], matrix[m-1][n-1]]之间对候选值mid统计矩阵中不大于它的元素个数cnt若cnt k说明答案偏大否则偏小。利用每行有序对每行只需扫描到第一个大于mid的元素即可public int kthSmallest(int[][] matrix, int k) { int m matrix.length, n matrix[0].length; int lo matrix[0][0], hi matrix[m - 1][n - 1]; while (lo hi) { int mid lo (hi - lo) / 2; int cnt 0; for (int i 0; i m; i) { for (int j 0; j n matrix[i][j] mid; j) { cnt; } } if (cnt k) lo mid 1; else hi mid - 1; } return lo; }复杂度每轮统计 O(m·n)内层循环受行有序性约束提前退出二分轮数为 O(log(max − min))总计 O(m·n·log(max − min)) 时间、O(1) 空间。注意中值写法lo (hi - lo) / 2与 二分查找 篇强调的一致l h可能加法溢出而h - l不会应使用后者。路线二小根堆归并 k 路有序序列由于每行有序矩阵等价于 m 路升序序列的归并问题先把首行 n 个元素全部入堆每次弹出堆顶当前最小把同一列的下一行元素补入堆顶所在的下一位置弹出 k 次后堆顶即第 k 小public int kthSmallest(int[][] matrix, int k) { int m matrix.length, n matrix[0].length; PriorityQueueTuple pq new PriorityQueueTuple(); for(int j 0; j n; j) pq.offer(new Tuple(0, j, matrix[0][j])); for(int i 0; i k - 1; i) { // 小根堆去掉 k - 1 个堆顶元素此时堆顶元素就是第 k 的数 Tuple t pq.poll(); if(t.x m - 1) continue; pq.offer(new Tuple(t.x 1, t.y, matrix[t.x 1][t.y])); } return pq.poll().val; } class Tuple implements ComparableTuple { int x, y, val; public Tuple(int x, int y, int val) { this.x x; this.y y; this.val val; } Override public int compareTo(Tuple that) { return this.val - that.val; } }复杂度堆大小不超过 n弹出 k 次共 O(k·log n) 时间、O(n) 空间。compareTo按val比较即构成小根堆当弹出的行已是最后一行t.x m - 1时没有下一个同列元素可补入直接continue。两种路线的取舍值域二分空间更省O(1)实现更短堆解法在 k 远小于 m·n 时更优且天然复用仓库中 Java 容器 篇讲解的PriorityQueue用法。该题也可视为 剑指 Offer 40 题最小的 K 个数 中堆解法找 Top-K思路在二维有序结构上的推广。6. 找出重复的数和丢失的数645 Set Mismatch, Easy数组长度为 n本应包含 1 到 n 的所有整数但其中一个数被另一个数替换导致出现一个重复数和一个丢失数要求找出它们。原文档示例Input: nums [1,2,2,4] Output: [2,3]最直接的方法是先排序再扫描时间复杂度 O(N log N)。原文档指出本题可以 O(N) 时间、O(1) 空间求解主要思想是通过交换使数组元素归位把nums[i]交换到下标nums[i] - 1值为 x 的数应该位于下标 x − 1直到当前位置放对或目标位置已有相同值说明发现重复public int[] findErrorNums(int[] nums) { for (int i 0; i nums.length; i) { while (nums[i] ! i 1 nums[nums[i] - 1] ! nums[i]) { swap(nums, i, nums[i] - 1); } } for (int i 0; i nums.length; i) { if (nums[i] ! i 1) { return new int[]{nums[i], i 1}; } } return null; } private void swap(int[] nums, int i, int j) { int tmp nums[i]; nums[i] nums[j]; nums[j] tmp; }复杂度O(n) 平均时间每个位置最多被交换常数次while 循环总次数有界、O(1) 空间。归位后扫描时nums[i] ! i 1的下标 i 处nums[i]是重复数、i 1是丢失数。该值域为 [1, n] 时以下标定位值的技巧与 剑指 Offer 3 题数组中重复的数字、Leetcode 题解 - 排序 篇的计数/交换类思想同出一源。7. 找出数组中重复的数287 Find the Duplicate Number, Medium数组长度为 n 1所有数在 1 到 n 之间且只有一个数重复可能出现多次要求不能修改数组、不能使用额外空间。原文档给出两种解法。解法一值域二分对值域 [1, n] 二分统计值 ≤ mid 的元素个数cnt若cnt mid说明 [1, mid] 这个只有 mid 个值的区间里挤进了超过 mid 个元素必有重复答案在左半区否则在右半区public int findDuplicate(int[] nums) { int l 1, h nums.length - 1; while (l h) { int mid l (h - l) / 2; int cnt 0; for (int i 0; i nums.length; i) { if (nums[i] mid) cnt; } if (cnt mid) h mid - 1; else l mid 1; } return l; }复杂度O(n log n) 时间、O(1) 空间。解法二快慢指针找环入口把数组看作函数映射 f(i) nums[i]从下标 0 出发不断跳转由于值域为 [1, n]n 1 个下标必有两个下标映射到同一个值序列中必然形成环重复数就是环的入口。这与 Leetcode 题解 - 双指针 篇一个指针每次移动一个节点一个指针每次移动两个节点如果存在环这两个指针一定会相遇的快慢指针判环思想一致原文档也明确注释类似于有环链表中找出环的入口public int findDuplicate(int[] nums) { int slow nums[0], fast nums[nums[0]]; while (slow ! fast) { slow nums[slow]; fast nums[nums[fast]]; } fast 0; while (slow ! fast) { slow nums[slow]; fast nums[fast]; } return slow; }第一阶段让快慢指针相遇确认存在环第二阶段把一个指针重置到起点 0两指针同速前进相遇点即环入口重复数。复杂度O(n) 时间、O(1) 空间同时满足不改数组、不用额外空间的约束。这一数组即函数图、找环入口即找重复值的建模是本题最值得记住的结论。8. 数组相邻差值的个数667 Beautiful Arrangement II, Medium题目要求用 1 到 n 的整数构造一个数组使相邻元素差值绝对值的不同取值恰好为 k 个。原文档示例Input: n 3, k 2 Output: [1, 3, 2] Explanation: The [1, 3, 2] has three different positive integers ranging from 1 to 3, and the [2, 1] has exactly 2 distinct integers: 1 and 2.构造思路是让前 k 1 个元素交替取两端值形成序列1, k1, 2, k, 3, k-1, ...其相邻差值恰好是k, k-1, ..., 1共 k 个不同值剩余位置按k2, k3, ..., n顺序填充相邻差值全为 1已包含在前 k 个差值中不引入新差值public int[] constructArray(int n, int k) { int[] ret new int[n]; ret[0] 1; for (int i 1, interval k; i k; i, interval--) { ret[i] i % 2 1 ? ret[i - 1] interval : ret[i - 1] - interval; } for (int i k 1; i n; i) { ret[i] i 1; } return ret; }复杂度O(n) 时间、O(1) 额外空间。interval从 k 递减奇数步加、偶数步减即可在 O(1) 内递推出生成前 k1 个摆动元素该构造法属于 Leetcode 题解 - 贪心思想 与构造类题目中先满足最难约束再退化填充的典型套路。9. 数组的度697 Degree of an Array, Easy数组的度定义为元素出现的最高频率例如[1,2,2,3,1,4,2]中 2 出现 3 次度为 3。题目要求找到与原数组度相同的最小长度子数组。原文档示例输入[1,2,2,3,1,4,2]输出6。解法用三个哈希表分别记录每个元素的出现次数、最后出现下标、首次出现下标满足度不变的子数组必须完整覆盖某个最高频元素的首末次出现区间答案即这些区间长度的最小值public int findShortestSubArray(int[] nums) { MapInteger, Integer numsCnt new HashMap(); MapInteger, Integer numsLastIndex new HashMap(); MapInteger, Integer numsFirstIndex new HashMap(); for (int i 0; i nums.length; i) { int num nums[i]; numsCnt.put(num, numsCnt.getOrDefault(num, 0) 1); numsLastIndex.put(num, i); if (!numsFirstIndex.containsKey(num)) { numsFirstIndex.put(num, i); } } int maxCnt 0; for (int num : nums) { maxCnt Math.max(maxCnt, numsCnt.get(num)); } int ret nums.length; for (int i 0; i nums.length; i) { int num nums[i]; int cnt numsCnt.get(num); if (cnt ! maxCnt) continue; ret Math.min(ret, numsLastIndex.get(num) - numsFirstIndex.get(num) 1); } return ret; }复杂度O(n) 时间、O(n) 空间哈希表规模等于元素种类数。核心结论是最小窗口一定由某个最高频元素的首末次出现撑开这与 Leetcode 题解 - 哈希表 篇中用哈希表把 O(n) 扫描的信息一次性聚合再按条件过滤的模式一致。10. 对角元素相等的矩阵766 Toeplitz Matrix, Easy托普利茨矩阵要求每条从左上到右下走向的对角线上所有元素相等。原文档示例1234 5123 9512 In the above grid, the diagonals are [9], [5, 5], [1, 1, 1], [2, 2, 2], [3, 3], [4], and in each diagonal all elements are the same, so the answer is True.每条对角线必然以第一行某个元素或第一列某个元素为起点因此只需从这两组起点出发、沿 (row1, col1) 方向递归校验整条对角线是否与起点值一致public boolean isToeplitzMatrix(int[][] matrix) { for (int i 0; i matrix[0].length; i) { if (!check(matrix, matrix[0][i], 0, i)) { return false; } } for (int i 0; i matrix.length; i) { if (!check(matrix, matrix[i][0], i, 0)) { return false; } } return true; } private boolean check(int[][] matrix, int expectValue, int row, int col) { if (row matrix.length || col matrix[0].length) { return true; } if (matrix[row][col] ! expectValue) { return false; } return check(matrix, expectValue, row 1, col 1); }复杂度O(m·n) 时间、O(min(m, n)) 栈空间递归深度为对角线长度。递归写法清晰表达沿对角线方向推进等价于迭代版本while (row m col n) { ...; row; col; }若不想占用调用栈可按 Java 虚拟机 篇对栈帧结构的理解自行改为迭代避免深矩阵下的递归深度问题。11. 嵌套数组565 Array Nesting, Medium给定元素为 0 到 n−1 的一个排列 A对每个下标 i 定义序列 S[i] {A[i], A[A[i]], A[A[A[i]]], ...}下标不断作为值再查表直到即将重复为止求所有 S[i] 的最大长度。原文档示例Input: A [5,4,0,3,1,6,2] Output: 4 Explanation: A[0] 5, A[1] 4, A[2] 0, A[3] 3, A[4] 1, A[5] 6, A[6] 2. One of the longest S[K]: S[0] {A[0], A[5], A[6], A[2]} {5, 6, 2, 0}从源码结构看解法把数组本身当作访问标记表沿 S[i] 前进时把经过的下标置为 −1下次外层循环遇到 −1 即停止内层推进从而每个下标只被访问一次总复杂度 O(n)public int arrayNesting(int[] nums) { int max 0; for (int i 0; i nums.length; i) { int cnt 0; for (int j i; nums[j] ! -1; ) { cnt; int t nums[j]; nums[j] -1; // 标记该位置已经被访问 j t; } max Math.max(max, cnt); } return max; }复杂度O(n) 时间、O(1) 额外空间但注意该实现会破坏输入数组原地标记 −1若题目要求不能修改数组可改用boolean[]访问标记以 O(n) 空间换取非破坏性。本质上 A 是一个 0~n−1 上的置换S[i] 就是 i 所在置换环的长度本题即求置换的最长环——与第 7 题的数组即函数图建模互为镜像。12. 分隔数组769 Max Chunks To Make Sorted, Medium给定 0 到 n−1 的一个排列允许把它划分成若干连续子块每块独立排序后拼接仍等于原排序数组求最多能划分多少块。原文档示例Input: arr [1,0,2,3,4] Output: 4 Explanation: We can split into two chunks, such as [1, 0], [2, 3, 4]. However, splitting into [1, 0], [2], [3], [4] is the highest number of chunks possible.判据是前缀最大值恰好等于当前下标记扫描到 i 为止的前缀最大值为right若right i说明前缀中所有 ≤ i 的数都已齐备因为排列中值域恰好是 0..n−1前缀内部怎么排序都会落在 [0, i] 区间内不会与后部交叉可以在 i 处切一刀public int maxChunksToSorted(int[] arr) { if (arr null) return 0; int ret 0; int right arr[0]; for (int i 0; i arr.length; i) { right Math.max(right, arr[i]); if (right i) ret; } return ret; }复杂度O(n) 时间、O(1) 空间。该题是 Leetcode 题解 - 双指针 类前缀聚合 条件切分的代表right就是前缀聚合状态right i就是切分条件若把数组换成含重复值的通用数组则需扩展为前缀最大值等于前缀内排序最大值的比较版本。技巧总结与延伸索引回顾 12 道题可归纳出数组与矩阵题型的几条主线写指针 / 双指针第 1、3 题读写分离或局部状态单遍扫描O(n) 时间 O(1) 空间的原地操作模板下标与值域的互化第 2、6 题index/n、index%n的矩阵一维化以及值在 [1, n] 时以下标定位值的原地归位利用单调性裁剪搜索空间第 4、5 题有序矩阵的右上角线性扫描、值域二分加计数、k 路归并小根堆三条路线可按 k 的大小与空间要求权衡快慢指针 / 环检测第 7 题把数组建成函数映射图Floyd 判环找入口是禁改数组 禁额外空间约束下的标准解哈希聚合第 9 题一次扫描聚合频次与位置信息二次扫描取最优原地标记第 11 题把输入数组本身当访问表置换环长统计前缀聚合判切分点第 12 题前缀最大值与下标相等即为合法切分。这些技巧在仓库的其他题解篇中有对应展开可按需延伸阅读Leetcode 题解 - 目录系列全部 200 题的分类导航与参考资料Leetcode 题解 - 双指针快慢指针判环、对撞指针等第 3、7 题相关技巧的更多题目Leetcode 题解 - 二分查找中值防溢出写法、查找区间等二分变体第 5、7 题二分解法的底层依据Leetcode 题解 - 哈希表第 9 题哈希聚合模式的更多应用Leetcode 题解 - 排序与交换归位、前缀判据相关的排序思想剑指 Offer 3 题数组中重复的数字 与 剑指 Offer 40 题最小的 K 个数值域定位与 Top-K 堆解法的姊妹题。需要说明的适用前提本文全部代码沿用原文档的 Java 实现JDK 1.8 的增强 for 循环、PriorityQueue等标准 API 即可运行第 11 题解法会原地修改输入数组实际使用时注意这一副作用各题复杂度分析基于 LeetCode 原题的输入约束如第 6、7 题的值域 [1, n] 前提若输入约束变化解法适用性需重新评估。【免费下载链接】CS-Notes:books: 技术面试必备基础知识、Leetcode、计算机操作系统、计算机网络、系统设计项目地址: https://gitcode.com/GitHub_Trending/cs/CS-Notes创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考