InterviewGuide 校招算法题解：力扣数组专题精选 23 题（Easy/Medium 分类速查与核心思路）

文档教程知识库【免费下载链接】InterviewGuide「InterviewGuide」是阿秀从校园-职场多年计算机自学过程的记录以及学弟学妹们计算机校招秋招经验总结文章的汇总包括但不限于C/C 、Golang、JavaScript、Vue、操作系统、数据结构、计算机网络、MySQL、Redis等学习总结坚持学习持续成长项目地址https://gitcode.com/forthespada/InterviewGuide点击查看免费下载导读本篇基于 InterviewGuide 仓库 03-leetcode/01-数组 目录 的「精选力扣 300 题目之数组」专题系统梳理其中已收录的 21 道 Easy、2 道 Medium 数组题解清单并为每道题提炼题目考点、易错点与仓库内题解给出的核心思路同时深入展开 5 道被原作者重点标注的经典题目第三大的数、最短无序连续子数组、数组形式的整数加法、等价多米诺骨牌对、盛最多水的容器的完整 C 题解演进过程。读完本文你将获得一份可直接对照仓库逐题练习的数组专题刷题地图并理解「暴力 → 优化 → 最优」这一贯穿校招算法面试的解题方法论。一、专题背景数组为什么是校招刷题的第一站在 InterviewGuide 的算法题库体系中数组专题位于 03-leetcode 之下与剑指 Offer、基础算法、高频算法等并列是「精选力扣 300 题目」计划中题目数量最多、难度梯度最友好的模块之一。仓库在该目录下建有easy/、medium/与hard.md三个子目录其中easy/收录 21 道题解、medium/收录 2 道题解hard.md目前仍标注为「阿秀正在加班加点的整理当中」见 hard.md。数组类题目之所以适合作为校招/社招刷题起点从仓库收录的题目特征可以直观看出三点覆盖基础数据结构操作遍历、双指针、滑动窗口、哈希计数、排序等高频手段在数组中几乎都能练到难度递进清晰从 414 第三大的数这类「O(n) 单次扫描」基础题到 989 数组形式的整数加法这类「大数加法 进位处理」实现题再到 11 盛最多水的容器这类「双指针 数学证明」思维题难度梯度完整与面试真题强相关如 581 最短无序连续子数组、605 种花问题等多道题目在原文档中被标注为「很经典的题目」「非常好的题」属于面试中反复出现的高频面孔。二、专题题目总览Easy 21 题 Medium 2 题速查表以下清单完整继承自 introduce.md并为每题补充考点与仓库内题解对应的文件路径。Easy 组21 题题号与题目核心考点仓库题解路径414. 第三大的数O(n) 单次扫描维护前三大去重LONG_MIN哨兵easy/414.第三大的数.md581. 最短无序连续子数组前后双趟扫描维护 max/min定位无序区间边界easy/581.最短无序连续子数组.md605. 种花问题连续 0 段长度与可种花数的换算防御式编程处理边界easy/605.种花问题.md628. 三个数的最大乘积排序后取 max(最大三正积, 两负一正积)注意负数easy/628.三个数的最大乘积.md643. 子数组最大平均数 I固定长度滑动窗口求最大均值easy/643.子数组最大平均数I.md665. 非递减数列单次违规后的修正策略贪心easy/665.非递减数列.md674. 最长连续递增序列单趟扫描统计连续递增段长easy/674.最长连续递增序列.md697. 数组的度哈希统计频次 首尾位置最小长度子数组easy/697.数组的度.md717. 1比特与2比特字符按编码规则单趟模拟判断末位归属easy/717.1比特与2比特字符.md724. 寻找数组的中心索引前缀和思想左右两侧和相等easy/724.寻找数组的中心索引.md747. 至少是其他数字两倍的最大数单趟扫描找最大值与次大值easy/747.至少是其他数字两倍的最大数.md830. 较大分组的位置单趟扫描连续相同字符段easy/830.较大分组的位置.md840. 矩阵中的幻方3×3 幻方判定中心为 5 的剪枝技巧easy/840.矩阵中的幻方.md849. 到最近的人的最大距离首尾连续 0 与中间连续 0 分段处理easy/849.到最近的人的最大距离.md888. 公平的糖果交换求和差推导交换条件 哈希查找easy/888.公平的糖果交换.md914. 卡牌分组频次统计 最大公约数easy/914.卡牌分组.md941. 有效的山脉数组严格递增后严格递减的单峰判定easy/941.有效的山脉数组.md989. 数组形式的整数加法大数加法 进位处理逆向逐位相加easy/989.数组形式的整数加法.md1089. 复写零双指针原地操作从后往前复写easy/1089.复写零.md1128. 等价多米诺骨牌对的数量无序对等价归一化 哈希计数easy/1128.等价多米诺骨牌对的数量.md剑指 Offer 66. 构建乘积数组左右两次前缀积O(n) 且不用除法easy/剑指Offer66.构建乘积数组.mdMedium 组2 题题号与题目核心考点仓库题解路径11. 盛最多水的容器双指针向内移动短板数学证明medium/11.盛最多水的容器.md1497. 检查数组对是否可以被 k 整除余数配对计数medium/1497.检查数组对是否可以被k整除.md说明原文档中「697. 数组的度」的链接地址写作easy/687.数组的度.md见 introduce.md而仓库实际文件名为 easy/697.数组的度.md属原文档中的编号笔误练习时以 697 题号与仓库实际文件为准。三、经典题解深度拆解五道被重点标注的题目原文档在目录中对部分题目使用了「很经典」「very nice」「很好的题」等标注本节挑选其中最典型的五道完整还原仓库题解的多版本演进过程。3.1 414. 第三大的数O(n) 扫描维护前三大题目给定一个非空数组返回其中第三大的数若不存在则返回最大的数。要求时间复杂度必须是 O(n)。原文档给出的示例揭示了本题的隐藏陷阱——「第三大且唯一出现的数」输入: [2, 2, 3, 1] 输出: 1 解释: 注意要求返回第三大的数是指第三大且唯一出现的数。 存在两个值为2的数它们都排第二。即重复元素只算一个排名[2,2,3,1]中 3 是最大、2 是第二大两个 2 并列、1 才是第三大。仓库题解第一版有参考的核心思想是用三个long long变量维护前三大并在单趟遍历中逐级「顺延」int thirdMax(vectorint nums) { long long firstNum LONG_MIN, secondNum LONG_MIN, thirdNum LONG_MIN; for (auto a : nums) { if (firstNum a) { thirdNum secondNum; secondNum firstNum; firstNum a; } else if (firstNum a secondNum a) { thirdNum secondNum; secondNum a; } if (secondNum a thirdNum a) { thirdNum a; } } if (thirdNum LONG_MIN) return firstNum; else return thirdNum; }要点分析初始值设为LONG_MIN而非 0是为了兼容数组中可能出现负数的场景保证比较逻辑正确三个分支分别处理「新最大值」「新第二大值」「新第三大值」三种插入情况且用严格的、判断天然过滤掉重复值相等元素不触发任何分支遍历结束后若thirdNum仍为LONG_MIN说明数组中不同数字不足三个按题意返回最大值firstNum时间复杂度 O(n)、空间复杂度 O(1)满足题目硬性要求。仓库记录该版执行用时 4 ms、击败 99.23% 的 cpp 提交内存消耗 9.1 MB击败 67.43%。这种「有限个哨兵变量 单趟扫描」的模式是解决 Top-K 类小规模问题K 固定且很小的通用套路。3.2 581. 最短无序连续子数组双向扫描定位无序区间题目给定一个整数数组找出一个连续子数组如果只对该子数组升序排序整个数组就会变为升序输出这个最短子数组的长度。原文档示例输入: [2, 6, 4, 8, 10, 9, 15] 输出: 5 解释: 你只需要对 [6, 4, 8, 10, 9] 进行升序排序那么整个表都会变为升序排序。核心思路原文档第一版注释从左到右遍历并记录当前最大值max若nums[i] max说明位置i处在无序段中记录该位置为low同理从右到左遍历记录当前最小值min若nums[i] min记录该位置为high。两个边界之间即为最短无序连续子数组。为什么这样能定位边界从源码逻辑看581.最短无序连续子数组.md正向扫描时一旦遇到比历史最大值小的元素说明它必然要被重新排序因为它破坏了「前面元素 ≤ 后面元素」的升序关系low不断向右刷新最终停在无序段的最右端反向扫描同理high最终停在无序段的最左端只要low high无序段长度就是low - high 1否则整个数组已有序返回 0。第三版将两个循环合并为单一循环左右同时推进int findUnsortedSubarray(vectorint nums) { if (nums.size() 1) return 0; int low 0, high nums.size() - 1, len nums.size(); int maxNum nums[0], minNum nums[high]; for (int i 1; i len; i) { maxNum max(nums[i], maxNum); if (nums[i] maxNum) { low i; } minNum min(nums[len - 1 - i], minNum); if (nums[len - 1 - i] minNum) { high len - 1 - i; } } return low high ? low - high 1 : 0; }仓库记录该版执行用时 28 ms、击败 98.19% 的 cpp 提交内存消耗 10.3 MB击败 97.12%相比第一版24 ms / 99.68%和第二版44 ms / 70.21%在单循环下兼具简洁与性能。该题的「双向极值扫描」思想正是排序问题中判断有序性的核心手段面试中常被延伸考查。3.3 989. 数组形式的整数加法大数加法的三版演进题目非负整数X的数组形式是其每位数字从左到右形成的数组如X 1231对应[1,2,3,1]。给定X的数组形式A与整数K返回X K的数组形式。原文档给出四组典型示例含全 9 进位场景输入A [1,2,0,0], K 34 输出[1,2,3,4] // 1200 34 1234 输入A [2,7,4], K 181 输出[4,5,5] // 274 181 455 输入A [2,1,5], K 806 输出[1,0,2,1] // 215 806 1021 输入A [9,9,9,9,9,9,9,9,9,9], K 1 输出[1,0,0,...,0]11 位约束1 A.length 10000、0 A[i] 9、0 K 10000且A.length 1时A[0] ! 0。数组最长可达 1 万位远超整型范围因此必须按位模拟加法而非整体转数值运算。第一版自己写的时间和空间都一般先把K逐位拆入临时数组temp再从A尾部与temp头部分段相加最后统一处理进位并reverse。代码通过 5 个 if 分支拼接结果逻辑较冗长仓库记录执行用时 180 ms击败 54.11%、内存 13.7 MB。第二版反而越改越差改为直接复用temp累加A[i]省去一个结果数组但执行用时反而升到 204 ms击败 47.70%。这说明「减少一个数组」并不必然带来性能提升算法优化要以实际测量为准——这也是仓库保留多个版本的价值所在它如实记录了真实刷题过程中「改来改去并不总是变好」的体验。第三版又改进了一下快多了直接把A就地反转将加法和进位合并到单趟循环中完成避免了额外的临时结果数组与多次遍历vectorint addToArrayForm(vectorint A, int K) { vectorint temp; while (K ! 0) { temp.push_back(K % 10); K K / 10; } reverse(A.begin(), A.end()); size_t i 0; for (; i A.size() i temp.size(); i) { A[i] temp[i] A[i]; if (A[i] 9 i ! A.size() - 1) { A[i] A[i] - 10; A[i 1] A[i 1] 1; } else if (A[i] 9 i A.size() - 1) { A[i] A[i] - 10; A.push_back(1); } } // 剩余位与最高位进位的收尾处理略 reverse(A.begin(), A.end()); return A; }该版执行用时降至 136 ms击败 95.79%、内存 12.3 MB击败 92.20%。三版对比清晰展示了从「分段拼接 后处理进位」到「原地反转 边加边进位」的优化路径其核心教训是进位应尽量在加法过程中即时处理避免二次扫描。3.4 1128. 等价多米诺骨牌对的数量从 O(n²) 到 O(n) 的哈希化归题目给定多米诺骨牌列表dominoes[a,b]与[c,d]等价当且仅当ac bd或ad bc即旋转 0° 或 180° 后相同。统计等价骨牌对(i, j)的数量。约束1 dominoes.length 40000、1 dominoes[i][j] 9。第一版直接遍历超出时间限制双重循环暴力两两比较复杂度 O(n²)在 40000 规模下必然 TLEint numEquivDominoPairs(vectorvectorint dominoes) { int cut 0; for (int i 0; i dominoes.size(); i) for (int j i 1; j dominoes.size(); j) if ((dominoes[i][0] dominoes[j][0] dominoes[i][1] dominoes[j][1]) || (dominoes[i][0] dominoes[j][1] dominoes[i][1] dominoes[j][0])) cut; return cut; }关键优化思路等价归一化。[a,b]与[b,a]等价因此把每张牌归一化为(min, max)的有序键等价关系就变成了键相等关系问题转化为「相同键的计数」。仓库给出了四种进阶实现逐步走向最优第二版自定义unordered_map键类型。定义struct KEY { int minNum; int maxNum; }并配套手写HashFunc对minNum与maxNum的哈希值做异或移位与EqualKey比较器将归一化键直接作为哈希键。执行用时 52 ms击败 87.56%。此版的价值在于展示了 C 中如何为自定义类型编写哈希函数与相等比较器。第三版整数编码键。由于每个数取值在[1,9]minNum * 10 maxNum可唯一表示一个归一化键用unordered_mapint,int即可。边遍历边累加「当前键已出现的次数」即为新增配对数。执行用时 48 ms击败 95.27%。第四版数学公式法。先统计每个键出现次数cnt再利用组合公式cnt * (cnt - 1) / 2一次性求出配对数。执行用时 44 ms击败 97.76%。第五版结合二、三、四版的精华最快的——整数编码 三元表达式归一化 组合公式执行用时 40 ms击败 99.00%、内存 21 MB击败 100.00%int numEquivDominoPairs(vectorvectorint dominoes) { unordered_mapint, int ret; int k 0, m 0, n 0; for (int i 0; i dominoes.size(); i) { m dominoes[i][0]; n dominoes[i][1]; (m n) ? k n * 10 m : k m * 10 n; // 归一化为 min*10max ret[k] 1; } int count 0; for (auto iter : ret) { count iter.second * (iter.second - 1) / 2; } return count; }规律总结当题目要求「无序对 / 等价对 / 旋转等价」计数时第一步永远是把对象归一化成唯一键第二步用哈希表计数第三步用组合公式聚合。这是数组哈希类题目的标准三步法。3.5 11. 盛最多水的容器双指针 短板移动的数学证明题目给定 n 个非负整数表示坐标中 n 条垂直线找出两条线与 x 轴构成容器能容纳最多水的方案输出最大水量。n至少为 2。示例[1,8,6,2,5,4,8,3,7]答案为 49。第一版速度太慢双重循环枚举所有(i, j)组合逐个计算(j - i) * min(height[i], height[j])执行用时高达 1640 ms仅击败 9.51%属于教科书式的 O(n²) 反面教材。第二版双指针很快左右指针从两端向中间收缩每次移动**高度较小短板**的一侧int maxArea(vectorint height) { int high height.size() - 1, low 0; int mostWater 0, temp; while (low high) { temp (high - low) * min(height[low], height[high]); mostWater mostWater temp ? mostWater : temp; if (height[low] height[high]) low; else high--; } return mostWater; }执行用时降至 16 ms击败 97.32%。为什么移动短板是正确的仓库在「比较经典的介绍」中给出了完整证明其核心逻辑可概括为设当前状态面积为S(i,j) min(h[i], h[j]) × (j - i)无论移动哪一侧底边宽度都减 1向内移动短板短板min(h[i],h[j])可能变大面积可能增大向内移动长板短板不变或变小面积一定不会增大该方向移动可安全丢弃因此每次移动短板本质上是在消去「以当前短板为界、另一侧所有更窄组合」的状态集而这些被消去的状态面积一定不大于当前面积故不会丢失最优解。从状态空间角度看暴力枚举的状态数为C(n,2)而双指针每次移动只保留可能更优的状态将复杂度降为 O(n)空间 O(1)。该题是「双指针 单调性」的入门代表理解其证明过程比背代码更重要面试追问「为什么移动短板是对的」时即可按此逻辑作答。四、其余高频题的解题要点速览为便于对照仓库逐题消化这里再补充几道被原文档标注为「好题」的题目的核心思路605. 种花问题flowerbed中1表示已种花0表示空地相邻地块不能都种。核心是把连续 0 段的长度换算成可种花数。仓库给出了两种解法第一版用unordered_map分段统计 0/1 计数第二版采用防御式编程——在数组两端各虚拟补一个 0这样「任意位置只要连续出现三个 0 就能种一朵花」代码大幅简化605.种花问题.md。849. 到最近的人的最大距离座位数组1有人、0为空。答案由三部分取最大左侧首段连续 0 的长度、右侧尾段连续 0 的长度、以及中间某段连续 0 的(len 1) / 2。仓库题解强调中间段的计算依据是「遇到 1 即结算当前连续 0 段」并且右端指针不能提前跳过849.到最近的人的最大距离.md。914. 卡牌分组统计每个数字出现次数若能找到X 2使所有频次都能被X整除则返回 true。易错点不能只判断「能否整除最小频次」例如[1,1,1,1,2,2,2,2,2,2]频次 4 和 6取X2是可行的。正确做法是求所有频次的最大公约数只要 GCD ≥ 2 即返回 true。仓库第二版用辗转相除法实现greatestCommonDivisor并在遍历中提前剪枝914.卡牌分组.md。五、总结数组专题的刷题方法论综合仓库 23 道题解可以沉淀出四条对校招面试直接可用的方法论先想暴力再谈优化仓库几乎所有题解都以「第一版暴力/朴素实现」开场如 1128 的 O(n²)、11 的双重循环、989 的分段拼接如实记录超时或低效的结果再逐步演进。刷题时先用朴素解法保证正确性再针对复杂度瓶颈优化。识别高频手段数组题的高频手段高度集中——单趟扫描维护哨兵极值414、747、674、双向扫描定位边界581、双指针11、1089、滑动窗口643、哈希计数与归一化键697、888、914、1128、前缀和/前缀积724、剑指 Offer 66。把每一类手段练熟就能覆盖绝大多数数组题。警惕边界与重复414 的「去重后排名」、581 的「升序含 ≤」、914 的「最大公约数而非最小频次整除」、989 的「最高位进位扩展」——这些细节正是面试中区分「会做」与「做对」的分水岭。版本对比是最好的复盘材料仓库题解保留了多版本演进与实测数据如 989 三版用时 180 ms → 204 ms → 136 ms提醒我们优化必须基于测量而非臆测建议读者每道题都先独立写出第一版再对照仓库的最优版复盘差距。六、延伸阅读数组专题目录与全部题目链接docs/notes/03-hunting_job/03-algorithm/03-leetcode/01-数组/introduce.md剑指 Offer 系列题解docs/notes/03-hunting_job/03-algorithm/02-sword-offerLeetCode 全量题解目录docs/notes/03-hunting_job/03-algorithm/03-leetcode基础算法专题docs/notes/03-hunting_job/03-algorithm/01-basic-algorithm面试八股文基础篇含数据结构总览docs/notes/03-hunting_job/02-interview赞分享文档教程知识库【免费下载链接】InterviewGuide「InterviewGuide」是阿秀从校园-职场多年计算机自学过程的记录以及学弟学妹们计算机校招秋招经验总结文章的汇总包括但不限于C/C 、Golang、JavaScript、Vue、操作系统、数据结构、计算机网络、MySQL、Redis等学习总结坚持学习持续成长项目地址https://gitcode.com/forthespada/InterviewGuide点击查看免费下载相关推荐InterviewGuide《精选力扣 300 道算法题》专栏全解析13 大标签分类、难度分级与高频考点实战指南InterviewGuide《精选力扣 300 道算法题》专栏全解析13 大标签分类、难度分级与高频考点实战指南 导读 本文围绕 InterviewGui文档教程知识库InterviewGuide 精选力扣 300 题解697. 数组的度——用哈希表定位「最短同度子数组」InterviewGuide 精选力扣 300 题解697. 数组的度——用哈希表定位「最短同度子数组」 本文是 InterviewGuide 仓库「 精选文档教程知识库校招八股文精选C 基础语法高频面试题 21-40InterviewGuide 实战解析校招八股文精选C 基础语法高频面试题 21 40InterviewGuide 实战解析 本文是 InterviewGuide「阿秀的学习笔记」校招八股文档教程知识库上一篇从0到1贡献Lepton开发者必备的代码规范与协作流程下一篇wandb业务价值跟踪量化ML实验对业务的影响创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考