LeetCode 217. Contains Duplicate 题解Go 语言哈希表判重的工程化实现与源码解析【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go本篇技术指南以 LeetCode 217 题「Contains Duplicate存在重复元素」为核心基于 LeetCode-Go 仓库中 leetcode/0217.Contains-Duplicate 的官方题解文档与 Go 源码实现完整讲解哈希表判重的解题思路、Go 代码的工程化细节map 预分配、逗号 ok 惯用法、提前返回、时间空间复杂度分析以及仓库内的测试验证方式。读完本文你将掌握一道面试高频「数组 哈希表」入门题的标准化 Go 实现并能直接复用该模式解决其余判重类题目。一、题目描述与示例LeetCode 217 题「Contains Duplicate」是数组与哈希表类别下的经典入门题原题如下Given an array of integers, find if the array contains any duplicates.Your function should return true if any value appears at least twice in the array, and it should return false if every element is distinct.即给定一个整数数组判断该数组中是否存在重复元素。只要任意一个数值在数组中出现至少两次函数就返回true若所有元素均互不相同则返回false。原文档给出的三个标准示例// 示例 1头部出现重复返回 true Input: [1,2,3,1] Output: true // 示例 2元素全部互异返回 false Input: [1,2,3,4] Output: false // 示例 3大量重复元素返回 true Input: [1,1,1,3,3,4,3,2,4,2] Output: true这三个用例恰好覆盖了三种典型场景重复出现在数组起始位置、全数组无重复、重复元素密集且多次出现是后续验证实现正确性的最小有效测试集。二、题目大意这是一道简单题如果数组里面有重复数字就输出true否则输出false。表面上是返回布尔值本质考察的是**在一组数据中快速判断「是否出现过」**的能力——这是哈希表最典型、最基础的应用场景也是后续大量滑动窗口、双指针、前缀和类题目的前置技能。三、解题思路哈希表Map判重原文档给出的解题思路非常精炼用 map 判断即可。核心思想是一条线性扫描的贪心判定遍历数组逐个元素检查若当前元素已经存在于 map 中说明此前出现过立即判定存在重复若不存在则将其记录进 map继续向后扫描扫描完整数组仍未发现重复则返回false。这种方法的关键优势在于map 的读写操作平均时间复杂度为 O(1)因此整个算法只需一趟遍历即可完成判定无需像排序法那样先付出 O(n log n) 的排序代价。四、仓库 Go 源码实现深度解析LeetCode-Go 仓库针对该题给出了一个非常简洁且工程化的实现位于 leetcode/0217.Contains-Duplicate/217. Contains Duplicate.gopackage leetcode func containsDuplicate(nums []int) bool { record : make(map[int]bool, len(nums)) for _, n : range nums { if _, found : record[n]; found { return true } record[n] true } return false }代码虽短却蕴含了三个值得细读的 Go 工程细节。4.1 预分配 map 容量make(map[int]bool, len(nums))创建 map 时显式传入容量len(nums)这是 Go 中典型的性能优化写法。make的第二个参数指定了 map 的初始容量bucket 数量当后续插入的元素数量不超过该容量时map 不会触发扩容rehash从而避免扩容带来的额外内存分配与元素重排开销。由于判重场景下 map 最坏会容纳全部 n 个元素直接用len(nums)作为容量是既合理又省心的选择——一次分配到位零扩容成本。作为对比若写成make(map[int]bool)而不指定容量Go 会以很小的默认容量创建 map插入过程中随元素增多会经历多次扩容虽然时间复杂度量级不变但常数开销更高。4.2 逗号 ok 惯用法if _, found : record[n]; foundGo 语言访问 map 时有两种取值形式单值形式v : m[k]在键不存在时会返回零值这里即false无法区分「键不存在」与「键存在但值为 false」两种状态。因此判重时必须使用双值comma ok形式v, found : m[k]其中第二个返回值found明确指出键是否真实存在。本实现中只关心「是否存在」不关心已存的值故用_丢弃第一个返回值。这是 Go 中判断元素是否存在的标准惯用法几乎所有需要判重的 Go 代码都遵循这一模式。4.3 提前返回early return与短路收益循环内部一旦发现重复立即return true不必继续扫描剩余元素。对于重复元素出现在数组前部的输入如示例 1 的[1,2,3,1]第二个元素扫描到索引 3 即命中这种提前返回能显著减少不必要的 map 写入操作是算法效率的常驻优化点。4.4 对应站点文档与实现一致性该实现与仓库站点文档 website/content/ChapterFour/0200~0299/0217.Contains-Duplicate.md 中展示的代码完全一致说明leetcode/目录下的题解源码即为站点文档的权威实现来源两者保持同步读者可放心对照学习。五、复杂度分析维度复杂度说明时间复杂度O(n)单趟遍历数组每次 map 读写平均 O(1)空间复杂度O(n)map 最多存储 n 个键值对每个键为int、值为bool时间上最坏情况无重复需要完整遍历 n 个元素最好情况第一个元素即重复只需常数次操作。空间上由于make预分配了容量len(nums)内存一次性到位占用与输入规模线性相关。这也是哈希表判重方案在「以空间换时间」上的典型体现。六、边界情况讨论一个健壮的实现应当正确处理以下边界输入空数组[]循环体不执行直接返回false——空数组不存在任何重复元素单元素数组[1]扫描唯一元素时 map 为空将其记录后循环结束返回false全相同元素[1,1,1]第二个元素即触发found true立即返回true负数与零int作为 map 键天然支持任意整数值负数、零均无需特殊处理大数组得益于 4.1 节的容量预分配即便输入规模很大也不会在扫描中途触发多次扩容。上述结论均可由源码结构直接推断该实现没有任何针对元素取值范围、正负号的假设对任意[]int输入均成立。七、测试与验证7.1 测试用例设计仓库为该题编写了对应的单元测试 leetcode/0217.Contains-Duplicate/217. Contains Duplicate_test.go测试结构与 README 中的三个示例一一对应qs : []question217{ {para217{[]int{1, 2, 3, 1}}, ans217{true}}, // 示例 1重复位于头部 {para217{[]int{1, 2, 3, 4}}, ans217{false}}, // 示例 2全部互异 {para217{[]int{1, 1, 1, 3, 3, 4, 3, 2, 4, 2}}, ans217{true}}, // 示例 3密集重复 }测试采用question217/para217/ans217三层结构分别承载「题目整体、入参、期望答案」并以表格驱动table-driven方式组织用例是 Go 社区推荐的测试风格。测试运行时按【input】:%v 【output】:%v的格式打印每个用例的输入与输出便于直观核对结果。7.2 运行测试与覆盖率在仓库根目录执行如下命令即可运行 leetcode 包下全部测试go test ./leetcode/...如需单独验证本题可指定包路径go test -v ./leetcode/0217.Contains-Duplicate/仓库还提供了脚本 gotest.sh其核心命令为go test -covermodeatomic -coverprofilecoverage.txt ./leetcode/...该脚本对 leetcode 全部包一次性生成单一合法的覆盖率文件coverage.txt仓库根目录可见。脚本注释中说明旧的按包逐个-coverprofile再cat追加的写法会产生重复的mode: atomic头导致 Codecov 解析失败Go 1.10 后改为一次命令直接产出单个合法 profile。这也是为什么本仓库能在 coverage.txt 中汇总全部题目的覆盖率数据——题解代码与测试共同构成了仓库「100% test coverage」声明的数据基础。八、延伸与其他判重方案的对比作为算法知识延伸除哈希表外判重问题还有几种常见思路各有适用场景以下为通用算法常识非仓库实现内容排序后相邻比较先排序再检查相邻元素是否相等。时间复杂度 O(n log n)、空间 O(1)原地排序适合对空间敏感且不介意排序开销的场景暴力双重循环O(n²) 时间、O(1) 空间仅适用于极小规模输入值域受限时的布尔数组若元素取值有明确且有限的范围可用[]bool代替 map进一步压缩空间并提升缓存友好性。对比之下哈希表方案以 O(n) 时间和 O(n) 空间取得了最优的时间复杂度且不依赖元素取值范围的任何假设是通用性最强、面试中最推荐的写法——这也是 LeetCode-Go 仓库为该题选择 map 方案的根本原因。九、总结LeetCode 217「Contains Duplicate」虽然是一道简单题但它浓缩了哈希表判重这一基础模式的完整套路单趟扫描 集合记录 命中即返。LeetCode-Go 仓库的实现源码在 12 行代码内完成了预分配容量、comma ok 判存在、提前返回三项工程化优化配合表格驱动的测试用例测试文件与覆盖率脚本gotest.sh为读者提供了一个可以直接照搬、可验证、可扩展的标准化模板。掌握本题后可将同样的 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），仅供参考