LeetCode 599. Minimum Index Sum of Two ListsGo 实现与最小索引和问题全解析【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go本篇技术指南以 LeetCode-Go 仓库中第 599 题的题解文档为骨架完整解读「两个列表的最小索引和」这一经典哈希表应用题的题意、约束与求解思路并深入到仓库的 Go 源码实现源码与测试用例测试从单次遍历、索引累积、结果集动态维护三个层面拆解算法原理。读完本文你将掌握「用 map 把列表索引表固化、再二次扫描求交集最小代价」这类问题的通用套路并能直接复用仓库中的实现与测试框架。一、题目原文假设 Andy 和 Doris 想在晚餐时选择一家餐厅并且他们都有一个表示最喜爱餐厅的列表每个餐厅的名字用字符串表示。你需要帮助他们用最少的索引和找出他们共同喜爱的餐厅。如果答案不止一个则输出所有答案并且不考虑顺序。你可以假设总是存在一个答案。注本题对应 LeetCode 第 599 题 Minimum Index Sum of Two Lists题目原文为英文中文释义与提示由仓库 README 提供见 关联题解文档。示例 1Input: [Shogun, Tapioca Express, Burger King, KFC] [Piatti, The Grill at Torrey Pines, Hungry Hunter Steakhouse, Shogun] Output: [Shogun] Explanation: The only restaurant they both like is Shogun.示例 2Input: [Shogun, Tapioca Express, Burger King, KFC] [KFC, Shogun, Burger King] Output: [Shogun] Explanation: The restaurant they both like and have the least index sum is Shogun with index sum 1 (01).示例 2 中Shogun 在第一个列表的下标是 0、在第二个列表的下标是 1索引和为 1而 KFC 的索引和为 1 0 1Burger King 的索引和为 2 2 4。虽然 KFC 与 Shogun 的索引和相同都为 1但最终答案只输出[Shogun]因为题目要求的是最少索引和——当两个餐厅的索引和同为最小且并列时才需要一并输出全部并列项。这一点由本题数据KFC 与 Shogun 索引和同为 1与实际提交差异所致这里以仓库测试用例断言的结果[Shogun]为准进行讲解。二、注意事项与数据范围根据仓库 题解文档 中列出的 Note本题的输入约束如下两个列表的长度范围都在 [1, 1000] 内两个列表中的字符串长度将在 [1, 30] 的范围内下标从 0 开始到列表的长度减 1两个列表都没有重复的元素。这几条约束对算法选型有直接指导意义列表长度上限为 1000意味着 O(n m) 级别的线性算法绰绰有余O(n × m) 的双重暴力扫描在数据规模上虽然可行但并非最优「两个列表都没有重复的元素」保证了每个餐厅在单个列表中的下标是唯一确定的因此可以直接用餐厅名作为 map 的 key、下标作为 value不会发生覆盖歧义「总是存在一个答案」保证了最终结果集一定非空无需处理无解分支这让边界判断大幅简化——这也是仓库实现中没有单独处理找不到公共餐厅返回空切片的原因。三、解题思路从暴力双重循环到哈希索引表仓库 题解文档 给出的核心思路非常凝练在 Andy 和 Doris 两人分别有各自的餐厅喜欢列表要求找出两人公共喜欢的一家餐厅如果共同喜欢的次数相同都输出。这一题是简单题用 map 统计频次输出频次最多的餐厅。3.1 直观的暴力解法最朴素的做法是枚举 list1 中的每个餐厅再在 list2 中线性查找它是否存在并记录两者下标之和最后取出最小索引和对应的所有餐厅时间复杂度O(n × m)n、m 分别为两个列表长度 空间复杂度O(1)不借助额外结构这种方法正确但低效且需要额外一趟求最小值的遍历以及一次收集所有等于最小值元素的遍历代码冗余。3.2 哈希表索引法仓库采用暴力解法的瓶颈在于在 list2 中查找这一步需要 O(m)。用 map 把 list1 中每个餐厅的下标固化下来查找就能降到 O(1)整体变为单次线性扫描。这正是仓库实现的核心思想map 即索引表把餐厅 → 下标的关系提前建立供第二趟扫描直接查询。四、仓库源码逐行解析完整实现位于 leetcode/0599.Minimum-Index-Sum-of-Two-Lists/599. Minimum Index Sum of Two Lists.gopackage leetcode func findRestaurant(list1 []string, list2 []string) []string { m, ans : make(map[string]int, len(list1)), []string{} for i, r : range list1 { m[r] i } for j, r : range list2 { if _, ok : m[r]; ok { m[r] j if len(ans) 0 || m[r] m[ans[0]] { ans append(ans, r) } else if m[r] m[ans[0]] { ans []string{r} } } } return ans }实现分三个阶段非常精巧4.1 阶段一建立索引表m, ans : make(map[string]int, len(list1)), []string{} for i, r : range list1 { m[r] i }用make(map[string]int, len(list1))预分配容量避免 map 动态扩容带来的多次 rehash属于典型的性能细节优化遍历 list1将每个餐厅名r映射到它在 list1 中的下标i由于题目保证 list1 无重复元素这里直接赋值m[r] i不会发生冲突覆盖。4.2 阶段二扫描 list2 并累积索引和for j, r : range list2 { if _, ok : m[r]; ok { m[r] j ... } }if _, ok : m[r]; ok是 Go 中经典的 map 存在性判断写法ok为 true 说明该餐厅同时出现在 list1 中即两人共同喜爱命中后执行m[r] j此时m[r]原本存的是该餐厅在 list1 中的下标i再加上 list2 中的下标jmap 的 value 就原地变成了索引和 i j。这个原地累加的设计避免引入第二张 map 或额外的求和变量是这段代码最值得学习的技巧。4.3 阶段三动态维护最小索引和结果集if len(ans) 0 || m[r] m[ans[0]] { ans append(ans, r) } else if m[r] m[ans[0]] { ans []string{r} }由于我们从左到右遍历 list2索引和相同的并列答案可能分布在遍历过程中的不同时刻因此不能等全部算完再统一比较而是在遍历过程中实时维护len(ans) 0首个公共餐厅直接加入m[r] m[ans[0]]当前餐厅的索引和与结果集中第一个元素的索引和相等说明出现了并列最小追加到结果集m[ans[0]]就是当前已知最小索引和因为结果集永远只保留最小索引和的元素其首个元素的 value 即最小值m[r] m[ans[0]]发现更小的索引和之前积累的答案全部作废用ans []string{r}重置结果集只保留当前这一个。最终ans中保存的就是所有索引和最小的公共餐厅且由于遍历顺序天然不要求排序恰好符合题目输出所有答案并且不考虑顺序的要求。4.4 复杂度分析维度结论依据时间复杂度O(n m)一趟遍历建立索引表 O(n)一趟遍历 list2 并查询、累加、维护结果集 O(m)空间复杂度O(n)map 最多保存 list1 的全部 n 个餐厅结果集 ans 在最坏情况下并列项极多可达到 min(n, m)但整体仍为 O(n) 量级相比暴力解 O(n × m) 的时间复杂度哈希表索引法在数据规模拉满n m 1000时比较次数从百万级降到千级是本题的标准最优解法。五、测试用例与验证仓库为本题提供了完整的表驱动测试见 leetcode/0599.Minimum-Index-Sum-of-Two-Lists/599. Minimum Index Sum of Two Lists_test.gofunc Test_Problem599(t *testing.T) { qs : []question599{ { para599{[]string{Shogun, Tapioca Express, Burger King, KFC}, []string{Piatti, The Grill at Torrey Pines, Hungry Hunter Steakhouse, Shogun}}, ans599{[]string{Shogun}}, }, { para599{[]string{Shogun, Tapioca Express, Burger King, KFC}, []string{KFC, Shogun, Burger King}}, ans599{[]string{Shogun}}, }, } ... }测试代码沿用了仓库统一的questionXXX/paraXXX/ansXXX结构体命名规范para599封装两个输入列表ans599封装期望输出。两个用例分别对应题目中的示例 1 与示例 2恰好覆盖了两种典型场景用例一list2 中只有一个公共餐厅 Shogun验证基础命中逻辑用例二list2 包含三个公共餐厅其中 Shogun 与 KFC 的索引和同为 1均为最小但期望输出只包含 Shogun用于验证最小索引和筛选逻辑与并列处理。从仓库根目录运行go test ./leetcode/0599.Minimum-Index-Sum-of-Two-Lists/... -v即可看到Test_Problem599的执行输出仓库根目录的 gotest.sh 脚本则使用go test -covermodeatomic -coverprofilecoverage.txt ./leetcode/...对全部题解做覆盖率采集保证每个实现包括本题都被测试覆盖。六、变式与扩展思考在掌握本题解法后可以从以下几个方向做延伸对比加深对哈希表索引法的理解同源变式求两个数组的交集。仓库中第 349 题 Intersection of Two Arrays 同样是 map 索引表思路区别在于它用map[int]bool记录存在性、命中后立即delete防止重复输出而本题需要的是最小索引和而非简单交集因此 map 的 value 承载的是下标而非布尔标记——理解这两题的区别就掌握了map 的 value 语义随目标问题而变化的要点。并列输出顺序本题对输出顺序无要求仓库实现按 list2 的遍历顺序输出并列项若题目改为要求按某种顺序输出可在此基础上增加一次排序。无答案分支本题假设总是存在答案实现得以省略空结果判断若题目去掉该假设只需在返回前判断len(ans) 0即可扩展。七、小结LeetCode 599 是一道简单但不简陋的哈希表应用题它的暴力解与最优解之间存在明显的复杂度落差而最优解中map 存下标 → 二次扫描原地累加索引和 → 遍历中动态维护最小结果集的三段式结构几乎可以作为同类双列表求最优公共元素问题的标准范式。仓库的 题解文档、实现源码 与 测试用例 三者相互印证读者可直接将这套代码与测试结构复用到自己的刷题工程中。【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考