文档教程后端【免费下载链接】interview-gogolang面试题集合https://interview.disign.me/项目地址https://gitcode.com/gh_mirrors/in/interview-go点击查看免费下载本文以 interview-go 仓库的 array-intersection.md 题解文档为主体结合仓库中可运行的 array-intersection.go 源码完整讲解 LeetCode 第 350 题「两个数组的交集 II」的两套解法哈希表HashMap计数法以及针对有序数组的双指针法。读完本文你将掌握带重复元素数组交集问题的两种经典思路、对应的 Go 实现细节、时空复杂度分析以及一套可直接运行的仓库级验证程序。01、题目回顾两个数组的交集LeetCode 350题目给定两个数组要求编写一个函数来计算它们的交集。示例 1输入: nums1 [1,2,2,1], nums2 [2,2]输出: [2,2]示例 2输入: nums1 [4,9,5], nums2 [9,4,9,8,4]输出: [4,9]说明输出结果中每个元素出现的次数应与元素在两个数组中出现的次数一致我们可以不考虑输出结果的顺序。进阶如果给定的数组已经排好序呢将如何优化你的算法呢这道题与「两个数组的交集 I」的关键区别在于结果必须保留重复元素。也就是说如果数字 9 在 nums1 中出现 2 次、在 nums2 中出现 2 次那么结果里也应当出现 2 个 9如果某个数字只在一个数组中出现则完全排除。示例 2 的输出[4,9]正是因此没有包含第二个9因为 nums1 中只有一个 9。这一约束直接决定了我们无法使用去重后的集合Set来解题而必须记录每个值的出现次数——这正是下文两种解法共同的出发点。02、解法一哈希表HashMap统计出现次数拿到这道题最直接的想法就是把它看成一道传统的映射题map 映射。为什么因为我们不仅需要找出两个数组的交集元素还要求结果中每个元素的出现次数与两个数组中的出现次数一致。这就导致我们需要知道每个值在两个数组中各出现了几次于是映射关系自然就变成了元素, 出现次数剩下的就是顺理成章地解题了。由于该种解法思路比较直接我们先梳理它的执行流程再给出完整题解。2.1 算法流程构建频次表遍历 nums1用哈希表记录每个元素出现的次数匹配并消费遍历 nums2若当前元素在哈希表中计数大于 0说明它同时出现在两个数组中将其加入结果并将哈希表中的计数减 1防止 nums2 中重复的元素超出 nums1 中的次数被误加入返回结果结果数组的长度由累计命中的次数决定。2.2 完整题解来自原文档func intersect(nums1 []int, nums2 []int) []int { m0 : make(map[int]int) for _, i : range nums1 { m0[i] 1 } k : 0 for _, v : range nums2 { if m0[v] 0 { m0[v] - 1 //这里是复用切片 nums2[k] v k } } return nums2[0:k] }这个方法比较简单相信大家都能看懂。这里有两个容易被忽略的细节值得展开计数减一m0[v] - 1是去重的关键假设 nums1 [2]、nums2 [2,2,2]如果不减计数结果会被错误地写成[2,2,2]。每命中一次就消费掉一次计数保证了结果中元素的个数严格等于两个数组出现次数的最小值复用输入切片nums2[k] v函数没有申请新的空白数组而是把命中元素原地写回 nums2 的前 k 个位置最后通过nums2[0:k]切片返回。遍历结束后 nums2 的原始内容已经不再需要这种空间复用手法在 Go 切片场景下非常实用。2.3 复杂度与优化点时间复杂度O(m n)其中 m、n 分别为两个数组的长度两次线性遍历空间复杂度O(m)哈希表记录了 nums1 中不同元素的个数。若将遍历计数和匹配消费的角色互换——用较短的数组建表、较长的数组去匹配理论上可把空间压到 O(min(m, n))这是从代码结构上可以直接推断的优化空间。03、解法二进阶排序数组的双指针法题目在进阶问题中问道如果给定的数组已经排好序呢你将如何优化你的算法我们分析一下。假如两个数组都是有序的分别为arr1 [1,2,3,4,4,13] arr2 [1,2,3,9,10]对于两个已经排好序的数组我们可以很容易想到使用双指针的解法因为数组有序两个指针各自只能前进、不能后退每次只需要比较两个指针指向的元素大小关系就能决定移动哪个指针从而在线性时间内完成交集求解。3.1 解题步骤步骤 1指针相等同时前进并记录结果。设定两个初始为 0 的指针 i、j比较两个指针指向的元素是否相等。如果指针的元素相等我们将两个指针一起向后移动并且将相等的元素放入空白数组。下图中我们的指针分别指向第一个元素判断元素相等1 1之后将相同元素放入结果。步骤 2指针不相等较小的指针后移。图中我们移到下一个元素继续判断若nums1[i] nums2[j]说明 nums2[j] 太小不可能与更大的 nums1[i] 相等将元素小的指针 j 向后移动继续判断反之nums1[i] nums2[j]则移动 i。步骤 3反复以上步骤。步骤 4直到任意一个数组终止。任一指针到达数组末尾i len(nums1)或j len(nums2)时说明较短的数组已被完全扫描剩余元素不可能再有交集循环结束。3.2 完整题解来自原文档根据上述分析我们很容易得到下面的题解func intersect(nums1 []int, nums2 []int) []int { i, j, m : 0, 0, 0 for i len(nums1) j len(nums2) { if nums1[i] nums2[j] { nums1[m] nums1[i] m i j } else if nums1[i] nums2[j] { j } else { i } } return nums1[:m] }提示解答中我们并没有创建空白数组因为遍历后的数组其实就没用了。我们可以将相等的元素放入用过的数组中这里复用的是 nums1 的前 m 个位置就为我们节省下了空间。3.3 复杂度分析时间复杂度O(m n)。两个指针最多各遍历完自己的数组一次空间复杂度O(1)忽略输出数组仅使用常数个指针变量且复用了 nums1 的空间。与哈希表解法相比双指针法在数组已有序的前提下空间占用更低、无哈希开销。而如果数组未排序则需要先排序调用 O(m log m n log n) 的排序算法后再执行 O(m n) 的双指针扫描。因此先排序 双指针适合数据量大且重复利用排序结果的场景而哈希表适合小数据量或无法排序如元素为不可比较类型的场景。04、仓库源码印证从题解到可运行程序文档中的两段题解在 interview-go 仓库中均有对应的可运行实现位于 algorithm/array-intersection.gomain函数L25-L35同时调用两种解法并打印结果intersect函数L38-L53哈希表解法与文档 02 节代码完全一致并保留了复用切片注释intersectSort函数L56-L72双指针解法与文档 03 节代码逻辑一致。仓库源码对题目示例做了一定的扩展用于更充分地验证重复元素的处理nums1 : []int{4, 9, 5, 9} nums2 : []int{9, 4, 8, 4, 9, 5, 5} fmt.Println(无序数组 -, intersect(nums1, nums2)) nums1 []int{1, 2, 3, 4, 5, 13} nums2 []int{1, 2, 5, 9, 10} fmt.Println(有序数组 -, intersectSort(nums1, nums2))第一组将示例 2 中的[4,9,5]扩展为[4,9,5,9]nums1 中有两个 9因此命中结果包含两个 9intersect实际输出为[9,4,9,5]元素顺序与 nums2 的遍历顺序一致满足不考虑输出顺序的要求很好地验证了按次数取交集而非去重取交集第二组[1,2,3,4,5,13]与[1,2,5,9,10]的交集为[1,2,5]intersectSort返回nums1[:3]验证了双指针解法在有序数组上的正确性。在仓库根目录可直接运行验证需本机已安装 Go 工具链go run algorithm/array-intersection.go05、延伸思考如果数组未排序怎么办进阶问题假设数组已经排好序但实际业务中我们更多遇到的是无序数组。此时有两条路线哈希表路线推荐不排序、直接映射O(m n) 时间完成无需改变输入数据排序 双指针路线若后续还要对同一批数据做多次交集、合并等操作可以先排序一次。仓库的 algorithm/sort 目录下恰好提供了经典的 冒泡排序、插入排序 与 选择排序 实现其对应的讲解文档见 algorithm/docs/bubble-sort.md、algorithm/docs/insertion-sort.md 与 algorithm/docs/selection-sort.md可用于对比理解先排序再双指针的整体开销。总结哈希表解法以元素, 出现次数为映射遍历一次建表、一次匹配用计数减一保证重复元素按最小出现次数计入结果时空复杂度 O(m n)、O(m)双指针解法适用于已排序数组指针相等则记录并齐步前进不相等则移动较小者直到任一数组遍历完时空复杂度 O(m n)、O(1)并通过复用输入切片省去额外数组两种解法均已收录在 interview-go 仓库的 array-intersection.go 中可配合 array-intersection.md 文档对照学习并直接运行验证。赞分享文档教程后端【免费下载链接】interview-gogolang面试题集合https://interview.disign.me/项目地址https://gitcode.com/gh_mirrors/in/interview-go点击查看免费下载相关推荐两个数组的交集LeetCode 0349哈希表与分离双指针解法详解 —— 出自「算法通关手册」AlgoNote两个数组的交集LeetCode 0349哈希表与分离双指针解法详解 —— 出自「算法通关手册」AlgoNote 本文以 0349. 两个数组的交集 htt教程文档知识库LeetCode 0350 两个数组的交集 II 题解哈希表计数与分离双指针实战AlgoNote 算法通关手册LeetCode 0350 两个数组的交集 II 题解哈希表计数与分离双指针实战AlgoNote 算法通关手册 给定两个数组 nums1 与 nums2教程文档知识库LeetCode 1748 唯一元素的和排序双指针与计数哈希表双解法详解LogicStack-LeetCodeLeetCode 1748 唯一元素的和排序双指针与计数哈希表双解法详解LogicStack LeetCode 本文是「刷穿 LeetCode」系列中 1教程文档上一篇Kedro 与 PySpark 集成实践从项目搭建、数据加载到并发调优的完整指南下一篇Linux 内核 Union-Find并查集实现解析从 uf_node 到 cpuset 调度域合并实战创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考