Learn-Algorithms 数列交并集面试题精讲：集合交集、有序数组合并与双序列和差最小化

• 教程

本文源自本仓库面试题笔记 5.3 数列-交并集.md，聚焦面试中高频出现的三类数列问题：两个集合的交集、两个有序数列的原地合并、以及通过交换使两个序列和之差最小。读完本文，你将掌握哈希表求交集 O(M+N) 的时空权衡思路、尾部向头部扫描的双指针原地归并技巧，以及"两序列和差最小化"背后的动态规划（背包）建模方法，并能对照仓库中的 HashTable.c 与 insert_sort.c 源码理解其底层实现。

一、题目全景：这类题考什么

在 5 数组数列问题.md 的开篇，笔记作者就总结了数组数列类题目的考察范围：数组排序、top-k、子数组、多个数组合并与交集。本文件 5.3 数列-交并集.md 正是其中"多个数组合并、交集"主题下的三个具体问题：

1. 如何求两个集合的交集；
2. 如何把两个有序数列合并（原地合并进容量足够的数组 A）；
3. 如何通过交换元素使两个序列的和之差最小。

三个问题分别对应三类解题思想：散列表空间换时间、双指针 + 分治归并、动态规划 / 贪心近似。这也是数组数列章节反复强调的解题工具箱（见 5 数组数列问题.md 中"解决这一类问题时可以从以下几个方面考虑"的列表：蛮力穷举、散列表空间换时间、分治后归并、堆排序求 top-k、排序后二分、贪心或动态规划）。

二、问题一：如何求两个集合的交集

2.1 原文档的提问与思路

原文档对第一个问题的记录非常精炼，但抓住了核心：

每个集合里面是否有重复元素？ 思路一：hash，复杂度 O(M+N)

这句话拆开来看其实是两个子问题：

• 前提判断：两个集合 A、B 中各自是否允许重复元素？如果"集合"在数学意义上不允许重复，则可以直接进入哈希去重逻辑；如果允许重复（更接近"数组/多重集"），则交集语义要明确——是"元素去重后的交集"还是"按出现次数取 min 的交集"。面试时先与面试官对齐这个前提，是这类题目的第一个得分点。
• 主解法：哈希表。遍历长度较小的集合（假设为 M），全部放入哈希表；再遍历另一个集合（长度 N），逐个查表，命中即加入交集结果。时间复杂度 O(M+N)，空间复杂度 O(M)（选择小集合建表可以优化空间）。

2.2 哈希表底层：仓库中的拉链法实现

为什么"hash"能给出 O(1) 的单次查询、从而让整体达到 O(M+N)？仓库 3 Hash Table/HashTable.c 给出了一个完整的哈希表实现，可以印证其原理：

// 拉链法实现，也就是链表的数组，也是数组和链表优势的结合 typedef struct HashTable{ Entry **head; // 桶数组，每个桶指向一条链表 unsigned int size; // 桶数量 unsigned int usage; // 已使用/已插入元素数 }HashTable;

typedef struct Entry { struct Entry *next; Hash hash; // key 对应的 hash 值 Key key; Value value; }Entry;

该实现采用拉链法（链地址法）：用size个桶组成数组，每个桶头挂一条链表，冲突的 key 挂在同一条链表上。查询时先由哈希函数定位桶，再沿链表比较 key——在负载因子合理的情况下，单次查找期望为 O(1)。这就是"空间换时间"的依据：付出 O(M) 的建表空间，换来 O(N) 次的近似 O(1) 查询，总代价 O(M+N)。

基于此，求交集的标准代码框架如下（以 Java 为例，可用HashSet充当哈希表）：

// 求两个集合（数组）的交集，输出去重后的交集元素 public static List<Integer> intersect(int[] a, int[] b) { Set<Integer> set = new HashSet<>(); for (int x : a) { // 遍历第一个集合，建表，O(M) set.add(x); } List<Integer> result = new ArrayList<>(); for (int x : b) { // 遍历第二个集合，查表，O(N) if (set.contains(x)) { // 查表期望 O(1) result.add(x); } } return result; }

优化提示：遍历时优先选择长度较小的集合建表，空间开销为 O(min(M,N))；如果题目还要求"按较小出现次数取交集"，则需要改用Map<元素, 次数>计数，第一遍统计次数、第二遍按min(count_a, count_b)输出——这与 5.4 数列-查找.md 中"找重复数先排序后遍历"的思路互为补充。

2.3 追问变体：两个有序数组的交集

面试官经常追加一问：如果两个数组已经有序，如何求交集？此时哈希法仍可行，但双指针更优：两个指针分别指向 A、B 的头部，比较当前值——相等则收集并同时后移；较小的一方后移。时间复杂度 O(M+N)，空间 O(1)，不需要哈希表。这与下文"合并两个有序数列"的双指针技巧一脉相承，属于同一套思想的正反两用。

三、问题二：合并两个有序数列

3.1 题目描述与示例

合并两个有序数列 A 和 B，其中 A 有足够的空间，也就是把 B 合并进 A 数组。

A = [4,5,6] B = [1,2,7] 合并后 A = [1,2,4,5,6,7]

这是经典题"Merge Sorted Array"的面试表述：A 的物理容量大于其有效元素个数（aSize），要把 B 的全部元素合并进 A，且合并结果仍然有序，空间复杂度要求通常为 O(1)（不使用额外数组）。

3.2 思路一：合并后归并排序（递归）

原文档给出的第一个思路是：

合并 2 个数列，变成[4,5,6,1,2,7]，归并排序即可，递归思路。

即先把 B 接到 A 的尾部拼成大数组，再对整个数组做归并排序。归并排序是分治（divide-and-conquer）的典型应用，仓库 6 Sort/README.md 中给出了它的框架，并点明其本质是"二叉树的后序遍历"：

分解 → 解决 → 合并 1. 分解：将一个数组分成 n/2 个子数组（2 路归并） 2. 解决：将各个子数组排好序 3. 合并：merge 两个有序数组，合并操作是 O(n)

void sort(int[] nums, int low, int high) { int mid = (low + high) / 2; sort(nums, low, mid); // 左半排好序 sort(nums, mid + 1, high); // 右半排好序 /****** 后序遍历位置 ******/ merge(nums, low, mid, high); // 合并两个排好序的子数组 /************************/ }

归并排序的merge操作本身复杂度就是 O(n)，而本题 A、B 各自已经有序，因此"先拼成大数组再整体归并排序"其实绕了远路——直接对两个有序段做一次 merge 即可，这正是思路二。

3.3 思路二：尾部向头部扫描（原地双指针）

原文档的思路二是：

尾部向头部扫描，将大的值放在尾部。

这是本题的正解，也是与"从头往尾合并"的关键区别：因为 A 的有效数据占在数组前部、尾部有空位，若从前往后 merge，A 的已有元素会被覆盖；从尾部向头部写，则大元素先落在数组末尾的空位上，永远不会覆盖尚未处理的元素，天然实现 O(1) 额外空间。

原文档给出的代码框架如下：

// 尾部向头部扫描，将大的值放在尾部 static void mergeSequenceList(int[] a, int aSize , int[] b){ int len_a = a.length -1; int index_a = aSize -1; int index_b = b.length -1; while (index_a >= 0 && index_b >= 0) { // 2个指针都有值时 if (a[index_a] >= 0 && b[index_b] >= 0) { if (a[index_a] > b[index_b]) { a[len_a--] = a[index_a--]; }else{ a[len_a--] = b[index_b--]; } } // a 无值，b有值；把剩下 b 放好 if (index_a < 0 && index_b >= 0) { while (index_b >= 0) { a[len_a--] = b[index_b--]; } } // a 有值，b 无值；把剩下 a 放好 if (index_a >= 0 && index_b < 0) { while (index_b >= 0) { // 原文此分支循环体为空 } } } }

3.4 原代码的两个缺陷与修正版

这份笔记代码作为思路标记是清晰的，但直接运行存在两个缺陷，面试现场写出可运行的完整版本才是加分项：

1. 用a[index_a] >= 0判断"是否有值"不严谨：当数组中包含负数元素时会误判，应直接用指针index_a >= 0判断元素是否已处理完；
2. 第三个分支逻辑写错了：index_b < 0时while (index_b >= 0)的循环体永远不会执行；且外层while (index_a >= 0 && index_b >= 0)一旦某指针为负就退出，剩余的拷贝逻辑必须在循环外补齐。

修正后的标准实现（以 Java 为例）：

/** * 将有序数组 B 合并进有序数组 A（A 容量充足） * @param a 目标数组，长度 >= aSize + b.length * @param aSize A 中有效元素的个数 * @param b 待合并的 B 数组 */ static void mergeSequenceList(int[] a, int aSize, int[] b) { int len = a.length - 1; // 从 A 物理末尾开始写 int i = aSize - 1; // A 有效元素区间的末尾 int j = b.length - 1; // B 的末尾 while (i >= 0 && j >= 0) { // 两指针都有值时，取大的放尾部 if (a[i] > b[j]) { a[len--] = a[i--]; } else { a[len--] = b[j--]; } } while (j >= 0) { // B 有剩余，直接拷到前面 a[len--] = b[j--]; } // A 有剩余时无需处理：a[0..i] 本就在数组最前部，位置天然正确 }

用原文档的示例验证：

A = [4,5,6,_,_,_] （a.length = 6，aSize = 3） B = [1,2,7] i=2 j=2：6 < 7 → 末尾写 7，j=1 i=2 j=1：6 > 2 → 写 6，i=1 i=1 j=1：5 > 2 → 写 5，i=0 i=0 j=1：4 > 2 → 写 4，i=-1 循环退出，j=1：拷入 2、1 结果 A = [1,2,4,5,6,7] ✓

3.5 仓库源码佐证：双路归并的 C 实现

本仓库 6 Sort/insert_sort.c 中实现了归并排序的两段式核心，其中merge_array函数与本题的"merge 两个有序段"逻辑完全同构（区别只是它借助临时空间）：

// 合并 2 个有序数组，分配一个临时空间装 a、b 的结果，最后将合并结果拷贝到数组 A void merge_array(int *a, int size_a, int *b, int size_b) { int *tmp = malloc((size_a + size_b) * sizeof(int)); int i, j, k; i = j = k = 0; while (i < size_a && j < size_b) { tmp[k++] = (a[i] > b[j]) ? b[j++] : a[i++]; // 每次取较小者 } while (i < size_a) { tmp[k++] = a[i++]; } // 左段剩余 while (j < size_b) { tmp[k++] = b[j++]; } // 右段剩余 for (int p = 0; p < k; ++p) { a[p] = tmp[p]; } // 拷回原数组 free(tmp); }

对比可见两种写法共享同一套骨架：两两比较取较小（较大）者 → 处理剩余段 → 收尾。区别只在存储策略：

• merge_array用临时数组（空间 O(M+N)），从前往后写，适合通用归并排序；
• 面试题版的mergeSequenceList利用 A 尾部的空位，从后往前写，零额外空间。

这也印证了 6 Sort/README.md 中的结论：两个有序数组的合并操作本身是 O(n) 的，归并排序的复杂度 O(nlogn) 完全由递归拆分的 logn 层堆叠而来——当输入已经是两个有序段时，一次 merge 就够，这是思路二优于思路一的根本原因。面试中建议先答思路一（归并排序框架，展示分治理解），再答思路二（尾部扫描，展示空间优化意识），最后给出完整可运行代码。

四、问题三：两个序列和之差最小

4.1 题目描述

有两个序列 a、b，大小都为 n，序列元素的值任意整数、无序； 要求：通过交换 a、b 中的元素，使 [序列 a 元素的和] 与 [序列 b 元素的和] 之间的差最小。

例如：

var a = [100, 99, 98, 1, 2, 3]; var b = [1, 2, 3, 4, 5, 40];

原文档只给出了题目与示例，没有给出解法。这是一个典型的"数组划分/负载均衡"类面试题，下面给出两条由浅入深的思路。

4.2 思路一：动态规划（01 背包）——精确解

关键观察：交换 a、b 中的元素，等价于从总共 2n 个数中重新挑选 n 个数放入 a（其余 n 个放入 b）。两个序列的和之差最小，就是要让选出的 n 个数之和尽量接近总和的一半total/2。

于是问题转化为经典 01 背包：

• 物品：全部 2n 个元素；
• 容量：total / 2；
• 限制：恰好选 n 件；
• 目标：所选元素之和尽量接近容量（不超过容量）。

设dp[k][v]表示"从前 k 件物品中选取若干件，件数恰好为某值、总和恰好为 v 是否可达"，或用三维滚动写法：dp[j][v] = 从前若干件中选 j 件凑出总和 v 是否可行。状态转移：

// 布尔背包：dp[j][v] = 能否选 j 个元素使总和恰为 v boolean[][] dp = new boolean[n + 1][total / 2 + 1]; dp[0][0] = true; for (int x : all) { // 遍历 2n 个元素 for (int j = n - 1; j >= 0; j--) { // 件数维度，倒序滚动 for (int v = total / 2; v >= x; v--) { if (dp[j][v - x]) dp[j + 1][v] = true; } } } // 从 total/2 往下找第一个 dp[n][v] == true 的位置 v // 最小差 = |total - 2*v|

复杂度 O(n²·total)，其中 total 是元素总和。当 n 较大但元素取值范围有限时，还可以用 bitset 压缩布尔数组，把状态压成位向量进一步提速。这是本题的精确解法，也是 8 Algorithms Analysis/动态规划.md 中"背包问题"模型的直接应用。

4.3 思路二：贪心交换——近似解

面试现场如果不要求精确解，可以先给出直观的贪心近似：

1. 计算当前sum_a、sum_b，记差值diff = |sum_a - sum_b|；
2. 反复寻找一对(a[i], b[j])，若交换后两序列和之差变小（即满足sum_a > sum_b时，选满足a[i] - b[j] > 0且尽量接近diff/2的一对交换），则执行交换；
3. 直到找不到能缩小差值的一对为止。

// 贪心交换：不断找一对元素交换以缩小和差，直到局部最优 while (true) { int diff = sumA - sumB; if (diff == 0) break; boolean improved = false; int bestI = -1, bestJ = -1, bestNewDiff = Math.abs(diff); for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { int newDiff = Math.abs(diff - 2 * (a[i] - b[j])); // 交换后差变化 2*(a[i]-b[j]) if (newDiff < bestNewDiff) { bestNewDiff = newDiff; bestI = i; bestJ = j; } } } if (bestI == -1) break; // 无法继续改善 // 交换 a[bestI] 与 b[bestJ]，并更新 sumA、sumB }

该思路的时间复杂度最坏为 O(n²·k)（k 为交换轮数），只能保证局部最优，不能保证全局最优；作为面试热身答案没问题，但应当主动补充"要精确解需用背包 DP"的进阶结论——先贪心给直觉、再 DP 给精确解，是这类开放题的最佳应答节奏。

4.4 示例推演

对题目给出的例子做一次直观观察：

a = [100, 99, 98, 1, 2, 3] → sumA = 303 b = [1, 2, 3, 4, 5, 40] → sumB = 55

sumA远大于sumB，显然应该把 a 中的大数（98、99、100）与 b 中的小数（1、2、3、4、5）大量交换，把两个序列的负荷"拉平"。这正是"交换使和差最小"问题的本质：把总量均分到两个序列上，让每个序列各承担接近 total/2 的和。用 4.2 节的背包模型，就是从 12 个元素中选出 6 个、使其和尽量接近(303+55)/2 = 179，此时最小差|total - 2v|即答案。

五、小结：一题一思想

三个问题串起来，正好覆盖数列类面试题的三条主线：

面试实战建议：

• 先对齐前提：集合有无重复、数组是否有序、A 的容量是否已知，直接决定解法选择；
• 先框架后细节：参考 9 Algorithms Job Interview/README.md 中总结的刷题框架（遍历、递归、双指针、二分、滑动窗口、排序、DP），先套框架再补边界；
• 代码要可运行：原笔记中的 merge 代码是思路示意，其中第三个分支存在空循环缺陷，正式回答务必给出修正版并口头验证示例数据；
• 主动谈优化：从"合并 + 归并排序"（思路一）到"尾部扫描原地归并"（思路二），从"贪心交换"（近似）到"背包 DP"（精确），每一次升级都是在展示复杂度与空间的分析能力，这正是面试官希望听到的思考轨迹。

• 教程