科学计算【免费下载链接】codeforces-go算法竞赛模板库 by 灵茶山艾府 项目地址https://gitcode.com/GitHub_Trending/co/codeforces-go点击查看免费下载导读本文以本仓库 leetcode/biweekly/119/a/README.md 为核心主体完整讲解 LeetCode 双周赛 119 场 A 题编号 2956「找到两个数组中的公共元素」的哈希集合解法核心思想是把数组转成哈希集合从而以 $\mathcal{O}(1)$ 时间判断元素是否在另一个数组中。文章将逐条展开题解中的算法步骤与复杂度分析原样保留 Python3 / Java / Java Stream / C / Go / JS / Rust 七种语言的完整参考实现并结合仓库内对应的 Go 源码、测试文件 与 测试数据从「哈希判重原理 → 逐语言实现 → 仓库自动化验证 → 相关数据结构拓展」四个层面讲透这道题读者读完可同时掌握此类「数组交集计数」题目的标准写法和本仓库的 LeetCode 解题工程化流程。题目定义与问题拆解题目来源LeetCode 双周赛 119 场 A 题「Find Common Elements Between Two Arrays」找到两个数组中的公共元素。题解在 README.md 开头就给出了一句高度概括的解题总纲把数组转成哈希集合就可以 $\mathcal{O}(1)$ 判断元素是否在数组中了。这句话点明了本题以及绝大多数「集合查询 / 交集 / 差集」类问题的核心优化手段用哈希表哈希集合的空间换取查询的常数时间。本题要求计算并返回两个统计量$\textit{answer}[0]$$\textit{nums}_1$ 中有多少个元素同时存在于 $\textit{nums}_2$ 中$\textit{answer}[1]$$\textit{nums}_2$ 中有多少个元素同时存在于 $\textit{nums}_1$ 中。注意这里的计数口径是遍历原数组、按每个元素逐一统计而不是统计去重后集合的交集大小。也就是说$\textit{nums}_1$ 中的重复元素会被重复计入这一点在后续边界情况一节会进一步验证。核心思路哈希集合的 $\mathcal{O}(1)$ 判重为什么选择哈希集合而不是嵌套循环如果采用朴素做法——对 $\textit{nums}_1$ 的每个元素遍历 $\textit{nums}_2$ 判断是否存在时间复杂度为 $\mathcal{O}(n \times m)$在 $n$、$m$ 达到 $10^5$ 量级时会退化到 $10^{10}$ 次比较无法通过。哈希集合的判重思路与之完全相反预处理阶段把待查询的数组一次性全部放入哈希集合查询阶段对每个元素只做一次哈希查找平均复杂度 $\mathcal{O}(1)$。整体代价从 $\mathcal{O}(n \times m)$ 降为 $\mathcal{O}(n m)$空间上只需额外存储两个集合 $\mathcal{O}(n m)$属于典型的以空间换时间。算法步骤详解题解给出了非常清晰的四步流程这里逐条展开第 1 步把 $\textit{nums}_1$ 中的元素加入哈希集合 $\textit{set}_1$ 中。遍历 $\textit{nums}_1$将每个元素插入 $\textit{set}_1$。由于集合天然去重即使 $\textit{nums}_1$ 内部有重复元素$\textit{set}_1$ 中每个元素也只会保留一份。第 2 步把 $\textit{nums}_2$ 中的元素加入哈希集合 $\textit{set}_2$ 中。对 $\textit{nums}_2$ 做同样的预处理得到去重后的 $\textit{set}_2$。第 3 步遍历 $\textit{nums}_1$统计在 $\textit{set}_2$ 中的元素个数即为 $\textit{answer}[0]$。此时 $\textit{set}_2$ 已经建好对 $\textit{nums}_1$ 的每个元素 $x$ 只需一次contains(x)判断Go 实现中利用 map 取值的零值语义见下文。命中则累加最终得到第一个答案。注意这一步是在原始数组 $\textit{nums}_1$ 上遍历因此 $\textit{nums}_1$ 中的重复元素会被重复计入——这是与集合交集大小的关键区别。第 4 步遍历 $\textit{nums}_2$统计在 $\textit{set}_1$ 中的元素个数即为 $\textit{answer}[1]$。对称地完成第二个统计量算法结束。多语言参考实现原题解完整代码题解为 7 种语言各提供了一份可直接提交的参考实现以下全部代码均继承自 README.md逐一对照可以帮助理解同一思路在不同语言中的惯用写法。Python3class Solution: def findIntersectionValues(self, nums1: List[int], nums2: List[int]) - List[int]: set1 set(nums1) set2 set(nums2) return [sum(x in set2 for x in nums1), sum(x in set1 for x in nums2)]Python 用set(nums1)一行完成建集合sum(生成器表达式)完成条件计数代码最简洁。Javaclass Solution { public int[] findIntersectionValues(int[] nums1, int[] nums2) { HashSetInteger set1 new HashSet(); for (int x : nums1) { set1.add(x); } HashSetInteger set2 new HashSet(); for (int x : nums2) { set2.add(x); } int[] ans new int[2]; for (int x : nums1) { if (set2.contains(x)) { ans[0]; } } for (int x : nums2) { if (set1.contains(x)) { ans[1]; } } return ans; } }Java 版本将四步流程写成最直观的四个循环HashSet.contains即为 $\mathcal{O}(1)$ 判重。Java Streamclass Solution { public int[] findIntersectionValues(int[] nums1, int[] nums2) { SetInteger set1 Arrays.stream(nums1).boxed().collect(Collectors.toSet()); SetInteger set2 Arrays.stream(nums2).boxed().collect(Collectors.toSet()); int cnt1 (int) Arrays.stream(nums1).filter(set2::contains).count(); int cnt2 (int) Arrays.stream(nums2).filter(set1::contains).count(); return new int[]{cnt1, cnt2}; } }Stream 版本用boxed()把基本类型装箱、Collectors.toSet()建集合filter(set2::contains).count()完成过滤计数属于 Java 8 的声明式写法。Cclass Solution { public: vectorint findIntersectionValues(vectorint nums1, vectorint nums2) { unordered_setint set1(nums1.begin(), nums1.end()); unordered_setint set2(nums2.begin(), nums2.end()); vectorint ans(2); for (int x : nums1) ans[0] set2.count(x); for (int x : nums2) ans[1] set1.count(x); return ans; } };C 用迭代器区间构造unordered_setcount(x)返回 0 或 1直接累加进ans。Go与仓库源码一致func findIntersectionValues(nums1, nums2 []int) []int { set1 : map[int]int{} for _, x : range nums1 { set1[x] 1 } set2 : map[int]int{} for _, x : range nums2 { set2[x] 1 } ans : [2]int{} for _, x : range nums1 { ans[0] set2[x] } for _, x : range nums2 { ans[1] set1[x] } return ans[:] }JavaScriptvar findIntersectionValues function(nums1, nums2) { const set1 new Set(nums1); const set2 new Set(nums2); const cnt1 nums1.reduce((cnt, x) cnt (set2.has(x) ? 1 : 0), 0); const cnt2 nums2.reduce((cnt, x) cnt (set1.has(x) ? 1 : 0), 0); return [cnt1, cnt2]; };JS 用new Set(nums1)直接由数组构造集合reduce累加计数。Rustuse std::collections::HashSet; impl Solution { pub fn find_intersection_values(nums1: Veci32, nums2: Veci32) - Veci32 { let set1 nums1.iter().cloned().collect::HashSet_(); let set2 nums2.iter().cloned().collect::HashSet_(); let cnt1 nums1.iter().filter(|x| set2.contains(x)).count() as i32; let cnt2 nums2.iter().filter(|x| set1.contains(x)).count() as i32; vec![cnt1, cnt2] } }Rust 用iter().cloned().collect::HashSet_()建集合filtercount完成计数。复杂度分析原题解给出的复杂度结论如下时间复杂度$\mathcal{O}(nm)$其中 $n$ 为 $\textit{nums}_1$ 的长度$m$ 为 $\textit{nums}_2$ 的长度。两次建集合各为 $\mathcal{O}(n)$ / $\mathcal{O}(m)$两次遍历计数同样为 $\mathcal{O}(n)$ / $\mathcal{O}(m)$总代价线性。空间复杂度$\mathcal{O}(nm)$。需要同时保存 $\textit{set}_1$ 与 $\textit{set}_2$ 两个哈希集合注意集合大小按去重后元素个数计算但最坏情况下所有元素互不相同故上界仍为 $nm$。仓库中的 Go 实现细节map 零值语义的巧妙复用本仓库在 leetcode/biweekly/119/a/a.go 中保存了这道题的 Go 版提交代码与题解中的sol-Go版本完全一致。这里有一个值得注意的 Go 惯用技巧ans : [2]int{} for _, x : range nums1 { ans[0] set2[x] }在 Go 中对map[int]int读取不存在的键会返回零值 0而set2中存在的键其值恒为 1。因此set2[x]天然充当了存在性指示器$x \in \textit{set}_2$ 时set2[x]为 1计数 1$x \notin \textit{set}_2$ 时set2[x]为 0计数 0。这样就把判断 累加两个动作合并成一条语句省去了显式的if分支。用map[int]int而非map[int]boolbool 不能直接做加法运算正是为了让查询结果可以直接参与算术累加。同样ans : [2]int{}先声明定长数组、最后return ans[:]转成切片也是 Go 中返回定长结果数组的常见写法。仓库自动化验证测试数据、测试框架与生成工具测试用例与数据文件仓库为每题维护一个纯数据文件 a.txt内容格式为「每两行输入 一行输出」的样例组本题包含两个用例输入输出nums1 [4,3,2,3,1]nums2 [2,2,5,2,3,6][3,4]nums1 [3,4,2,3]nums2 [1,5][0,0]手工验证第一个用例nums1中同时出现在nums2的元素有2两个3不在nums24、1也不在共3个nums2中同时出现在nums1的元素有2,2,2,3共4个结果[3,4]正确。同时注意nums1中的两个3都不在nums2nums2中的三个2都命中说明重复元素按原数组逐一遍历计数验证了前文对计数口径的分析。测试框架RunLeetCodeFuncWithFile测试入口 a_test.go 依赖仓库自建的 LeetCode 测试工具链func Test_a(t *testing.T) { targetCaseNum : 0 // -1 if err : testutil.RunLeetCodeFuncWithFile(t, findIntersectionValues, a.txt, targetCaseNum); err ! nil { t.Fatal(err) } }其底层实现在 leetcode/testutil/leetcode.go#L340-L370RunLeetCodeFuncWithFile读取数据文件、按函数签名输入参数个数 返回值个数对行分组构造用例再通过反射驱动被测函数并逐条比对输出。targetCaseNum传 0 表示全量运行所有用例传 -1 则可用交互模式定位失败用例。测试文件头部还注释了本题在力扣上的两个页面编号双周赛页与题库页便于溯源。测试生成流程像 a_test.go 这类文件开头标注的Code generated by copypasta/template/leetcode/generator_test.go表明题目目录、测试文件与数据文件是由仓库的生成器自动产出的。生成逻辑见 copypasta/template/leetcode/generator_test.goTestBiweekly通过力扣账号环境变量LEETCODE_USERNAME_ZH/LEETCODE_PASSWORD_ZH自动抓取下一场双周赛题目并生成到leetcode/biweekly/{场次}/目录本场 119 的a/b/c/d四题即由此流程落盘见 leetcode/biweekly/119 目录结构。由此仓库内每道题都形成了「README 题解 提交代码 测试文件 纯数据文件」四件套任何解法修改都可以一键go test回归验证。思路拓展哈希判重的常见替代与进阶方向哈希集合判重思路在算法竞赛与力扣题中应用极广仓库的 copypasta 目录提供了若干可直接复用或对照学习的相关实现值域紧凑时的空间优化当元素值域较小如 $0 \le x \le 10^5$时可以用布尔数组代替哈希集合把 $\mathcal{O}(nm)$ 的哈希空间压缩为固定大小的 $\mathcal{O}(V)$ 数组。这种做法本质上仍是预处理后 $\mathcal{O}(1)$ 查询思想的体现。位集Bitset判重对于更极端的集合内元素判重/子集判断场景仓库提供了完整的位集实现 copypasta/bitset.go。它用(n_w-1)/_w个机器字_w bits.UintSize按位存储元素Has/Set/Reset/Flip均为 $\mathcal{O}(1)$ 位运算并支持Or/And/Xor等集合运算与Next1/Next0遍历适合在大集合上做批量交并操作。两种容器的取舍哈希集合适合值域大、稀疏、需要灵活增删的判重位集/布尔数组适合值域小、稠密、追求极致常数的判重。本题两种数组长度与值域均未给极值约束哈希集合是最稳妥、可读性最高的通用方案。总结本题的解法链条非常清晰数组 → 哈希集合 → 逐数组遍历判重计数。整个算法只用两次建集合和两次线性扫描时间复杂度 $\mathcal{O}(nm)$、空间复杂度 $\mathcal{O}(nm)$配合原题解中 7 种语言的参考实现属于一题吃透哈希判重模板的典型样例。而本仓库围绕这道题沉淀的 题解文档、Go 提交代码、自动化测试 与 测试数据 四件套也为读者展示了刷题 工程化验证的完整闭环任何尝试改写例如改用布尔数组或位集都可以通过go test在本地立即验证正确性。赞分享科学计算【免费下载链接】codeforces-go算法竞赛模板库 by 灵茶山艾府 项目地址https://gitcode.com/GitHub_Trending/co/codeforces-go点击查看免费下载相关推荐5个高效Bash数组交集实战技巧快速找出两个数组的共同元素5个高效Bash数组交集实战技巧快速找出两个数组的共同元素 Bash数组交集是Bash脚本编程中处理数据集合的核心技能掌握这一技巧能帮助开发者高效对比数据、教程Hugo 模板函数 collections.Intersect 完全指南求取两个序列的公共元素Hugo 模板函数 collections.Intersect 完全指南求取两个序列的公共元素 本指南深入讲解 Hugo 模板集合函数 collections开发工具前端CLILeetCode 215 数组中的第 K 个最大元素最小堆与 QuickSelect 多语言解法全解leetcode 仓库实战LeetCode 215 数组中的第 K 个最大元素最小堆与 QuickSelect 多语言解法全解leetcode 仓库实战 本文围绕 LeetCode示例工程教程上一篇用Python代码创造Minecraft世界5个惊艳的自动化创意下一篇Rerun 0.9 迁移指南从分散的 log_* 函数到统一的 Archetype 日志 API创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考