《合并表记录》在笔试算法题库里属于那种“看着简单、实则常挂”的题目。我既做过刷题陪练也在招聘环节筛过不少候选人见过太多人栽在这道题上有人想都不想就开大数组结果 index 一大直接内存溢出有人用哈希表合并完忘了排序输出顺序乱掉还有人连输入换行都没处理干净整个输出错位。这篇文章就把这道题从头到尾拆开——它到底在考什么、有哪些隐蔽的坑、标准解法怎么写、面试现场怎么答才加分。不管你是准备校招笔试的新手还是想找回手感的老开发都能从里面挖到点干货。1. 这道题到底在考什么1.1 题目背景与真实场景映射先还原一下题目长什么样。输入第一行给一个正整数 n表示后面有 n 行数据每行包含一个 index 和一个 value。要求把所有 index 相同的记录合并value 累加求和最后按 index 升序输出合并后的键值对。举个最基本的例子输入 4 0 1 0 2 1 3 1 4输出 0 3 1 7第一行的 4 表示有四条记录0 和 1 这两个 index 各出现了两次所以各自加起来。用一句话概括这道题给一堆键值对同键求和、按键排序。这其实就是数据库里 GROUP BY 加 SUM 做的事情也是订单汇总、日志聚合、流量统计里最常用的处理逻辑。很多在线评测平台把它归为入门级哈希表题但它出现在笔试里非常合理——笔试系统需要一道能快速区分“会不会写代码”和“有没有工程意识”的题这道题两头都能测出来。1.2 输入输出格式里的暗坑题目本身不长但笔试里至少有三种输入变体标准版是第一行给 n后面跟 n 行数据有些平台改成不给 n一直读到 EOF还有的平台会在数据里混进多余的空格、空行甚至行首缩进。如果不先确认输入格式就闷头写 while(scanner.hasNext())碰到标准版输入时程序会把第一行那个 n 也当成记录去处理或者读完 n 之后把第一条数据吞掉输出直接错得莫名其妙。我在实际辅导中见过至少三位同学挂在这个第一行的 n 上原因是他们习惯了那种“没有输入数量、直接给数据”的无数量题目遇到有 n 的格式反而不会读了。输出格式也有讲究每一行输出“index value”index 和 value 之间用空格隔开行尾不要有多余空格最后一行也要换行。听起来像废话但有些笔试系统的判题是逐字节比对多一个空格、少一个换行就是 Wrong Answer。1.3 这道题适合谁来练它非常适合两类人。第一类是准备校招笔试的新手因为这道题同时覆盖了哈希表、排序、输入输出三个基础点而且代码量短是性价比很高的入门题。第二类是社招想快速找回手感的老手用来热身和检验编码习惯——有没有处理边界情况、有没有考虑数值溢出、有没有在动手前先确认数据范围。很多工作三五年的开发写业务代码没问题但一上机就暴露坏习惯比如不读题直接写、不看数据范围乱选数据结构这道题恰好能把这些毛病全挑出来。2. 思路拆解三种解法的选择逻辑2.1 数组下标映射只适合 index 范围小的场景拿到题的第一反应通常是开一个数组用 index 当下标直接累加最后遍历数组输出非零项。这个思路不是错但有一个大前提index 必须落在合理范围内。原题里 index 是 int 范围内的整数不是 0 到 100 的小数。如果 index 能到几千万甚至上亿直接开这么大的数组内存当场爆炸。就算 index 全是正数且最大只有一万你也得先扫描一遍数据找到最大值再决定数组开多大或者额外维护一个布尔数组记录哪些下标出现过代码复杂度反而上去了。我的实际建议是只有在确知 index 范围很小比如题目明说 0 到 10000 以内或者你能从输入样例推断出最大值可控时才用数组。笔试现场追求的是稳妥和速度动手前先问一句“index 范围多大”比写完发现数组越界再回来改要快得多。这个问题我后面还会反复强调因为它就是这道题真正的分水岭。2.2 哈希表聚合标准且稳妥用哈希表把 index 作为 keyvalue 作为累加器是这道题最标准也最稳妥的答案。每读一行数据就在哈希表里找这个 index存在就把 value 加进去不存在就放入新的键值对。这样内存占用只跟去重后的 key 数量有关而跟 index 的取值范围完全无关。n 最多 1000 的题目去重后撑死 1000 个 key空间极其可控。最后把 key 排个序输出结束。这里有个细节值得展开如果直接用 Java 的 TreeMap它本身就按 key 升序维护插入完整个 map 就已经有序省掉了最后单独排序那一步。但 TreeMap 的插入是 O(log k)而 HashMap 是平均 O(1)最后单独对 key 排序一次是 O(k log k)。在 n 只有 1000 的情况下两者性能差距完全可忽略但面试时你能说出这个权衡说明你是真懂而不是背模板。2.3 先排序再合并另一种不可忽视的思路不建哈希表也能做把所有 (index, value) 读进一个数组按 index 排序然后从头到尾扫一遍相邻且 index 相同的累加合并遇到不同的 index 就把前一组输出。时间复杂度是排序主导的 O(n log n)空间 O(n)。相比哈希表它多花一点时间但少用一点随机访问在某些没有现成哈希库、或者哈希表性能很差的受限环境下反而是更主流的选择。我在 C 语言笔试里就经常推荐这个写法因为 C 标准库没有哈希表但 qsort 是现成的。把三种解法放在一起对比选型逻辑就很清楚了解法时间复杂度空间复杂度适用场景数组下标O(n 最大Index)依赖 index 范围index 范围小且明确哈希表聚合O(n k log k)O(k)k 为去重后 key 数通用笔试首选排序合并O(n log n)O(n)无哈希库、数据量小2.4 思路背后的本质聚合思维这道题的本质不是算法技巧而是一种聚合思维key 到 value 的多对一映射。你每天在业务代码里写的“按用户分组统计消费金额”“按渠道汇总点击量”“按错误码统计失败次数”全都是这个模式。只不过业务里你可能用 SQL 的 GROUP BY或者用流式框架的 reduce 操作而笔试里让你用最原始的数据结构手动实现一遍。所以别把它当成一道背答案的水题理解了这个“分组求和”的思维模型你在任何语言里都能写出对应的实现。3. 核心代码实现与细节剖析3.1 Java 标准答案TreeMap 一行省掉排序Java 里最省事的写法是直接用 TreeMap它天然按 key 升序排列最后遍历输出即可import java.util.*; public class Main { public static void main(String[] args) { Scanner sc new Scanner(System.in); int n sc.nextInt(); MapInteger, Long map new TreeMap(); while (n-- 0) { int index sc.nextInt(); long value sc.nextLong(); map.put(index, map.getOrDefault(index, 0L) value); } for (Map.EntryInteger, Long e : map.entrySet()) { System.out.println(e.getKey() e.getValue()); } } }这里我故意用了 Long 而不是 Integer原因后面专门讲。getOrDefault 这个 API 避免了你先 containsKey 再 get 的两步操作代码简洁还不会写错。如果想用 HashMap 展示你对两种 Map 的理解那就合并完后把 keySet 拿出来 Collections.sort 再输出效果一样只是多两行代码而已。3.2 Python 版本读取方式决定稳不稳Python 版的关键在输入读取。我强烈推荐用 sys.stdin.read().split() 一次性把整个输入切成 token 列表然后用下标偏移量取数先读 n再循环 n 次每次取两个 token。这样写的好处是彻底不在乎换行符、行尾空格、空行这些破事数据哪怕被拆成一百行也没关系你只按 token 顺序取就行。相比之下用 for i in range(n): input().split() 也能跑但一旦某行有多余空格或空行就容易取错行数。import sys def main(): data sys.stdin.read().split() if not data: return n int(data[0]) mp {} pos 1 for _ in range(n): idx int(data[pos]) val int(data[pos 1]) pos 2 mp[idx] mp.get(idx, 0) val for k in sorted(mp): print(k, mp[k]) if __name__ __main__: main()合并逻辑就一行mp[k] mp.get(k, 0) v。最后 sorted(mp) 默认按 key 升序排逐行输出即可。Python 的 int 没有溢出问题所以这里不用像 Java 那样操心类型。3.3 C 版本的取舍map 还是 unordered_mapC 里有两种主流写法。用 map插入自动排序代码最短用 unordered_map插入平均 O(1)但最后得把 key 收集到 vector 里排一次序。n 等于 1000 时性能差距无关痛痒但面试官很喜欢追问这个选择。我的习惯是直接上 map理由是语义清晰、代码短笔试现场少写一行是一行。如果你非要展示对哈希表的理解用 unordered_map 再手动排序也完全没问题。#include bits/stdc.h using namespace std; int main() { int n; cin n; mapint, long long mp; while (n--) { int k, v; cin k v; mp[k] v; } for (auto p : mp) { cout p.first p.second \n; } return 0; }注意 mp[k] v 这行能成立是因为 map 的 operator[] 在 key 不存在时会默认插入一个 value 0所以 不会出错。这个特性很方便但也藏着一个坑如果你只是想知道 map 里有没有某个 key千万别用 operator[] 去判断因为它的副作用是“没有就插入”你查完之后 map 里就多了一个默认元素。判断存在性要用 count 或 find。3.4 数值溢出的隐藏风险这一点必须单独强调。题目说 value 是 int 范围内的正整数n 最大可以到 1000。如果极端情况下每个 value 都接近 21 亿1000 个累加完全可能超过两万亿早就超出 int 范围了。虽然多数评测数据不会这么变态但为了稳健我建议累加结果一律用 long 或 long long 存储。我自己第一次写这题时就用 int 存累加值后来在一套较真的测试数据上翻车才养成了“看到求和先想溢出”的条件反射。这个习惯在后面的笔试里救过我很多次。4. 实战中踩过的坑与排查思路4.1 第一个坑Scanner 读完整数后的换行残留用 Java 的 Scanner 时很多人习惯先 nextInt() 读 n再用 nextLine() 读每一行。问题来了nextInt() 读完数字后换行符还留在缓冲区里紧接着的 nextLine() 会把这个空行读走导致第一条数据直接丢失。解决方案有两个一是不要混用 nextLine全部用 nextInt() 按整数读二是如果非要按行读就在 nextInt() 之后补一个 sc.nextLine() 把残留换行吃掉。这个坑在笔试里出现频率极高因为它不是逻辑错误而是输入 API 的底层行为问题平时不写控制台程序的人根本遇不到。4.2 第二个坑排序方向与输出格式不一致TreeMap 默认升序HashMap 排序时要记得用默认的升序。有人为了秀操作写 Comparator.reverseOrder() 变成降序输出就跟题目要求相反。还有人在输出时写成 e.getKey() e.getValue()忘了中间的空格或者用 println 输出时在行尾多打了空格。这些细节在本地 IDE 里看不出来拷贝到在线评测系统就是全错。我的建议是输出前把样例跑一遍肉眼核对格式别急着提交。4.3 第三个坑map 合并时的默认值陷阱合并逻辑看起来简单但有个隐蔽的默认值问题。用 containsKey 写分支当然可以但啰嗦且容易漏分支用 getOrDefault 简洁但要注意 value 的类型默认值比如 Java 里 getOrDefault(key, 0) 返回 Integer如果你存的是 Long得写 0L。C 的 operator[] 前面说过判断存在性是 count 不是 operator[]。这些细节单独拎出来都不难但笔试时间紧、人又紧张最容易在这种地方翻车。4.4 第四个坑不清楚输入变体导致死循环或漏读有些笔试平台不给 n输入是 EOF 结尾。如果你按有 n 的写法读会把第一行的数据当 n 处理后面的全乱套。反过来题目给了 n你按 EOF 读虽然结果可能碰巧对但会多读一行数据。稳妥做法是先看题目描述里“输入描述”那一段明确是有 n 还是无 n。如果题目描述模糊就在代码里兼容两种先读一个 token 当作 n再循环 n 次同时判断还有没有下一行。笔试系统就算输入格式有小差异这种兼容写法也能兜住。4.5 常见问题速查表症状可能原因解决办法输出少一条记录nextLine 读到残留换行统一用 nextInt 或吞掉残留换行输出顺序和样例相反排序方向写反确认 TreeMap 默认升序 / 修改 Comparator大 value 累加结果变成负数int 溢出用 long / long long 存储累加值数据行有空行导致读取错位按行读被空行干扰用 read().split() 按 token 读输出格式全错空格或换行不对先跑样例对照格式再提交5. 笔试现场怎么答才能加分5.1 动手前先确认约束条件很多候选人上来就写五分钟写完提交结果挂了。真正的高分做法是动手前先跟面试官确认几个问题index 的范围是多少value 的范围是多少n 的上限输出一定要升序吗这些问题不是装样子而是直接决定数据结构选型。确认完 index 范围小你大可放心用数组确认完 value 可能很大你自然知道要用 long。这套“先问范围再选结构”的习惯是工程师和做题家的分水岭。我自己面试时候选人如果能主动问出数据范围印象分会立刻拉高。5.2 复杂度分析要讲透写完代码后面试官一定会问复杂度。标准答案哈希表阶段每条记录插入平均 O(1)n 条就是 O(n)排序阶段对去重后的 k 个 key 排序是 O(k log k)总时间 O(n k log k)空间 O(k)k 是去重后的 key 数量。如果使用 TreeMap插入是 O(log k)总时间 O(n log k)在 n 和 k 都小时没差别但你能主动讲出这个差异说明你真的理解数据结构而不是背答案。空间上要强调 O(k) 而不是 O(n)因为哈希表只存去重后的 key这个细节很多人说不清。5.3 扩展问法的准备面试官如果觉得不过瘾会加追问。常见的扩展方向有三个。第一内存受限时怎么办原始数据很大、内存放不下整个哈希表就需要外部排序或分桶聚合——把 index 哈希到多个桶里每个桶分别聚合再合并。第二要求保持原始出现顺序怎么办用一个 LinkedHashMap 或者额外维护一个插入顺序列表输出时就不排序而是按首次出现顺序。第三如果 index 是字符串而不是整数怎么办哈希表的 key 类型换成字符串就行逻辑完全不变。能答出这三个扩展这道题基本就满分了。6. 最后再分享一个判断习惯《合并表记录》刷完之后真正留下的是一个判断习惯写任何数据处理代码之前先问自己三个问题——数据从哪来、范围多大、要什么顺序。我后来带过的不少同学都是从这道题开始才慢慢学会在动手前花三十秒列约束条件而不是上来就写。这个习惯比会做十道题都值钱。笔试里的水题往往不是真的水它只是把工程里的常见问题剥到只剩骨架看你有没有那个意识去填肉。下次再遇到这类“简单题”不妨多问自己一层为什么收获会比想象中大得多。