LeetCode-Go 题解：1396 Design Underground System —— 双哈希表实现地铁平均通勤时间统计-育师

LeetCode-Go 题解：1396 Design Underground System —— 双哈希表实现地铁平均通勤时间统计

【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go

导读

本文以 LeetCode 第 1396 题「Design Underground System（设计地铁系统）」为对象，基于本仓库 LeetCode-Go 中该题的 README 题解文档与对应 Go 实现源码展开讲解。你将掌握：如何用两张哈希表在 O(1) 时间内完成乘客进站、出站记录与任意两站间平均旅行时间的查询，理解"直接行程"聚合统计的数据结构设计思路，并看到仓库内测试用例如何验证实现正确性。这是一道典型的"设计类 + 哈希表"题目，其思想可迁移到打车平台计价、物流轨迹统计等按起终点聚合求均值的真实场景。

题目理解与接口契约

题目要求实现UndergroundSystem类，模拟一个地铁系统对乘客进站出站的记录，并提供任意两个站点之间平均旅行时间的查询能力。三个方法的语义如下：

checkIn(int id, string stationName, int t)：编号为id的乘客在时刻t进入站stationName。一个乘客同一时间只能在一个站进站或出站，即进站后未出站前不能再次进站。
checkOut(int id, string stationName, int t)：编号为id的乘客在时刻t离开站stationName。
getAverageTime(string startStation, string endStation)：返回从startStation直接到达endStation的所有历史行程的平均耗时。题目保证被查询的路线至少已经存在一趟行程，且所有调用按时间顺序发生，出站时刻恒大于进站时刻。

"直接到达"是本题统计口径的关键：只有一次checkIn(start)到一次checkOut(end)完整对应的一段旅程才计入平均值，不允许中途换乘的拼接。这一语义直接决定了下面双哈希表设计的聚合维度。

示例推演

以文档中的 Example 1 为例，完整操作序列为：

checkIn(45, "Leyton", 3) checkIn(32, "Paradise", 8) checkIn(27, "Leyton", 10) checkOut(45, "Waterloo", 15) checkOut(27, "Waterloo", 20) checkOut(32, "Cambridge", 22) getAverageTime("Paradise", "Cambridge") // 14.00000 getAverageTime("Leyton", "Waterloo") // 11.00000 checkIn(10, "Leyton", 24) getAverageTime("Leyton", "Waterloo") // 11.00000（10 号乘客尚未出站，不纳入统计） checkOut(10, "Waterloo", 38) getAverageTime("Leyton", "Waterloo") // 12.00000

其中getAverageTime("Leyton", "Waterloo")在第三次查询时返回12.00000，计算过程为：((15-3) + (20-10) + (38-24)) / 3 = 36 / 3 = 12，可见三次完整行程都被累计。Example 2 则展示了多次查询逐步收敛平均值的场景：5.00000 → 5.50000 → 6.66667，分别对应累计 1、2、3 趟行程。

数据规模与约束

总操作次数最多20000次；
乘客 id 与时刻 t 满足1 <= id, t <= 10^6；
站名由大小写英文字母和数字组成，长度1 <= stationName.length <= 10；
答案与实际值的误差在10^-5量级内即可判为正确（文档原约束写作105，即 1e-5 精度要求）。

20000 次操作意味着即使采用 O(n²) 的暴力存储每次行程再遍历求均值也能通过，但题目考察的是"设计"能力——能否用更优雅、查询恒为 O(1) 的增量聚合方案。

核心解题思路：两张哈希表增量聚合

文档解题思路给出的方案是维护2 个 map：

mapA（乘客进站表）：存储乘客id与(入站时间, 入站站名)的对应关系。每次checkIn时写入。
mapB（路线统计表）：以"起点站 → 终点站"为键，存储该路线的累计总耗时 sum与行程次数 count。每次checkOut时，用出站时间减去该乘客入站时间得到本趟耗时，累加进sum、count加一，同时把该乘客从mapA中删除（乘客完成旅程，进站记录作废）。

最终getAverageTime(start, end)只需从mapB取出该路线的sum / count即可，无需遍历任何历史行程。

这种设计最精妙之处在于：平均值可以在线增量维护。因为avg = sum / count只依赖两个聚合量，而不是依赖全部原始行程列表，所以无论某条路线累积了多少趟行程，查询代价恒定。这也让"存储全量行程 + 每次遍历求和"的冗余做法失去了必要。

逐步状态推演（结合 Example 1）

三次checkIn后，mapA中有三条记录：45 → (Leyton, 3)、32 → (Paradise, 8)、27 → (Leyton, 10)。
checkOut(45, "Waterloo", 15)：取到45的进站信息(Leyton, 3)，将路线Leyton → Waterloo的sum += 12, count++，随后删除mapA[45]。
同理checkOut(27, "Waterloo", 20)使Leyton → Waterloo变为sum = 22, count = 2；checkOut(32, "Cambridge", 22)使Paradise → Cambridge变为sum = 14, count = 1。
此时getAverageTime("Leyton", "Waterloo")返回22 / 2 = 11.0，与示例输出11.00000完全一致。
checkIn(10, "Leyton", 24)仅写入mapA[10]，不影响Leyton → Waterloo的聚合数据，故再次查询仍为11.00000；直到checkOut(10, "Waterloo", 38)之后，路线聚合变为sum = 36, count = 3，查询返回12.00000。

Go 源码逐段解析

仓库中完整实现位于 1396. Design Underground System.go，与文档 README 中的代码一致，属于包leetcode下的标准解法。

数据结构定义

type checkin struct { station string time int } type stationTime struct { sum, count float64 } type UndergroundSystem struct { checkins map[int]*checkin stationTimes map[string]map[string]*stationTime }

checkin对应文档中的"乘客进站表"单条记录，封装入站站名与入站时刻。
stationTime对应"路线统计表"的聚合值：sum累计总耗时、count累计行程数，两者均为float64，避免后续除法时出现整数截断。
UndergroundSystem结构体持有两张 map：checkins以乘客 id 为键；stationTimes采用二级嵌套 map（起点站 → 终点站 → 聚合值），天然表达"起终点对"这一复合键，省去了手写结构体键或拼接字符串的开销。

构造函数

func Constructor() UndergroundSystem { return UndergroundSystem{ make(map[int]*checkin), make(map[string]map[string]*stationTime), } }

返回结构体值而非指针，后续方法均以指针接收者(s *UndergroundSystem)调用，保证 map 引用共享。注意两个 map 都需要显式初始化，否则向 nil map 写入会触发 panic。

CheckIn：记录进站

func (s *UndergroundSystem) CheckIn(id int, stationName string, t int) { s.checkins[id] = &checkin{stationName, t} }

O(1) 写入乘客的进站快照。由于题目保证"一个乘客同一时间只能进站一次"，这里直接覆盖赋值即可，无需处理重复进站冲突。

CheckOut：聚合路线耗时并清理进站记录

func (s *UndergroundSystem) CheckOut(id int, stationName string, t int) { checkin := s.checkins[id] destination := s.stationTimes[checkin.station] if destination == nil { s.stationTimes[checkin.station] = make(map[string]*stationTime) } st := s.stationTimes[checkin.station][stationName] if st == nil { st = new(stationTime) s.stationTimes[checkin.station][stationName] = st } st.sum += float64(t - checkin.time) st.count++ delete(s.checkins, id) }

这段代码对应文档思路中"每当有人checkout()，就更新mapB中的信息，并删除mapA对应乘客 id 的键值对"：

从checkins取出该乘客的进站记录（题目保证存在且唯一）；
检查二级 mapstationTimes[进站站名]是否已初始化，未初始化则先创建（懒加载，避免构造函数中预先铺开所有站点组合）；
检查该路线的聚合节点是否存在，不存在则new(stationTime)创建；
将t - checkin.time（本趟耗时）转成float64累加进sum，count自增；
delete(s.checkins, id)删除进站快照——乘客已离站，进站记录使命完成，同时释放内存、避免过期数据被误用。

GetAverageTime：O(1) 求均值

func (s *UndergroundSystem) GetAverageTime(startStation string, endStation string) float64 { st := s.stationTimes[startStation][endStation] return st.sum / st.count }

直接取出路线聚合值做除法。由于题目保证查询的路线至少已有一趟行程，count恒大于 0，不存在除零风险；若对未出现的路线调用，st为 nil 会 panic，但这在题目约束下不会发生。

调用约定

源码末尾保留了 LeetCode 要求的接口调用模板注释：

/** * Your UndergroundSystem object will be instantiated and called as such: * obj := Constructor(); * obj.CheckIn(id,stationName,t); * obj.CheckOut(id,stationName,t); * param_3 := obj.GetAverageTime(startStation,endStation); */

注意 Go 方法名为大写开头的导出方法（CheckIn/CheckOut/GetAverageTime），这与 LeetCode 其他语言的小写签名只是命名风格差异，语义一一对应。

复杂度与正确性分析

操作	时间复杂度	空间复杂度
`checkIn`	O(1)	O(1)
`checkOut`	O(1)	O(1)
`getAverageTime`	O(1)	O(1)

时间：三个方法都只做常数次哈希表读写，均为 O(1)。整体处理 20000 次操作的总复杂度为 O(N)，远优于"存储每次行程、查询时全量遍历"的 O(N) 查询方案。
空间：checkins最多同时保存 N 个在途乘客；stationTimes最多保存 N 条路线的聚合节点。总体空间复杂度 O(N)，其中 N 为操作次数。

正确性关键点：

平均值在线可聚合：avg = sum / count，两条路线各自的sum、count相互独立，累加顺序不影响最终结果，因此增量维护不会引入误差累积之外的错误。
"直接行程"语义：聚合键是(startStation, endStation)完整起终点对，Leyton → Cambridge与Leyton → Waterloo是两个独立条目，天然不会把中转拼接到一起，严格契合题目"直接到达"的统计口径。
in-flight 乘客隔离：未出站的乘客只存在于checkins中，不参与任何路线聚合，因此getAverageTime永远只统计已完成的完整旅程（见 Example 1 中 10 号乘客在途时查询结果不变的推演）。
精度：sum、count使用float64，即便 20000 次操作全部集中于一条路线，sum 的量级也仅为20000 × 10^6 = 2×10^10，远在float64精确整数表示范围（2^53 ≈ 9×10^15）之内，满足题目10^-5的精度要求。

测试用例验证

仓库为该题配套了测试文件 1396. Design Underground System_test.go，其测试函数Test_Problem原样复现了 README 中的两个官方示例：

Example 1 场景：三次进站、三次出站后，依次断言Paradise → Cambridge返回14.00000、Leyton → Waterloo返回11.00000；随后插入"10 号乘客进站但未出站"的中间态，验证查询结果仍为11.00000（在途乘客不影响均值）；待其出站后断言结果更新为12.00000。这一段恰好覆盖了"聚合只统计完整行程"的核心语义。
Example 2 场景：同一路线Leyton → Paradise连续三趟行程，验证平均值随累计行程数平滑演进：5.00000 → 5.50000 → 6.66667，对应(8-3)/1、(8-3+16-10)/2、(8-3+16-10+30-21)/3的逐步累加。

测试通过fmt.Println打印每次查询输出，可直接对照题目给定的 Output 数组逐项核对。在仓库根目录执行go test ./leetcode/1396.Design-Underground-System/ -v（或运行仓库自带的 gotest.sh 脚本批量执行全部测试）即可复现验证。

延伸思考：设计类题目的通用范式

UndergroundSystem属于典型的"设计一个支持增量聚合查询的系统"类题目，其方法论可归纳为三步：

识别查询维度：getAverageTime按"起终点对"查询，因此聚合键必须是(start, end)二元组；
识别生命周期状态：乘客从进站到出站构成一次完整事务，需要一个临时表（checkins）记录 in-flight 状态，事务提交（出站）时把增量写入聚合表并销毁临时记录；
用聚合量替代明细：均值只需sum与count，不需要保留每次行程的明细列表，从而把查询从 O(n) 降到 O(1)。

同样的模式可迁移到：打车平台的路线平均计价（起终点对聚合金额与单数）、物流系统的站点间平均运输时长、埋点系统的接口平均耗时统计等场景。理解"在线增量聚合"这一思想，比记忆本题的代码本身更具长期价值。

参考资源

题目题解文档：leetcode/1396.Design-Underground-System/README.md（含题目原文、中文大意、完整示例与代码）
Go 源码实现：1396. Design Underground System.go
测试用例：1396. Design Underground System_test.go
仓库总览与刷题目录：README.md

【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go

创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考