C语言数组题：找出两个数组非共有元素的三种解法

1. 这道数组题到底在考什么

“4-29找出不是两个数组共有的元素”，光看这个标题，估计刚入门的同学会觉得是个简单遍历题，两个for循环互相查一下不就完了？但实际动手敲代码的时候，你会发现这里面埋了好几个坑。先说说我当年第一次做这类题的感受：题目描述只有一句话，可样例一跑，WA（答案错误）得莫名其妙。后来我才意识到，这道题真正想考察的并不是“会不会用for”，而是三件事：数组元素的遍历与标记思想、重复元素去重、输出格式的精确控制。

从所属的章节位置来看，第4章基本是C语言数组的内容，第29题说明出题人已经默认你掌握了数组的定义、初始化、一维数组遍历这些基础。顺着这个思路做下去，我发现它其实是“集合运算”的入门级变体：等价于求两个集合的对称差（symmetric difference），也就是只属于其中一个集合、不属于另一个集合的所有元素。听起来高大上？别被术语吓到，实质上就是“两个数组里，找出只在一边出现过的数”。

这道题的适用人群很明确：正在刷C语言/Java数组题的学生、准备机考或面试基础题的新手，甚至是想复习一下数组、标志位思想的从业者。它不像后面的链表、二叉树那样有复杂的指针操作，但恰恰是这类基础题最能暴露出你对边界条件和逻辑细节的掌控力。

我先给你透个底：这道题的标准解法有三条路，暴力双重循环、排序后双指针、利用哈希表或集合去重。每条路的代码量、时间复杂度和踩坑程度都不一样。我会一个个拆开讲，然后重点带你走一遍最稳、最好理解的暴力法，再把优化方案作为进阶补充。

2. 思路选型：为什么先暴力反而更稳

2.1 先把“共有”和“非共有”彻底掰扯清楚

什么叫“两个数组共有的元素”？字面上理解：一个数既出现在数组A中，又出现在数组B中，那它就是共有元素。反过来，“不是两个数组共有的元素”包括两种情况：

• 只出现在数组A中，不在数组B中；
• 只出现在数组B中，不在数组A中。

但这里有个隐蔽的坑：如果数组A里有两个3，数组B里有一个3，那么你是把3当作共有元素剔除，还是两个3分别判断？再进一步，如果A里有两个5，B里一个5都没有，输出是输出一次5还是两次5？

从常规题目的输出样例来看，最终输出结果中元素不应该重复。这就涉及“去重”：先判定归属关系，再考虑重复出现的情况。我见过很多同学在这里栽跟头：判定的时候发现A中有个元素不在B中，直接printf，完全没考虑A里这个元素出现了两次，结果输出了一串重复数字，跟标准答案对不上。

2.2 三种思路的取舍对比

我用一张表把三条路线的特点整理清楚，再逐个说明：

暴力法的优点在于逻辑直白，适合绝大多数基础题的数据规模（通常N和M最多几十）。它最大的问题是嵌套循环导致时间复杂度偏高，如果数据量到10万级别，两层循环就直接超时。

排序法解决的是“查找慢”的问题：先排好序，再用两个指针各自往后走。它的思路很像归并排序里的合并过程，但要多处理去重和对称差两个细节，代码容易写出边界错误。

哈希表/集合法在C语言里没有现成的标准库（C99和C11都没有内置哈希表），要么自己实现，要么用C++的STL容器。如果用Python，一行set运算就解决了；用Java，HashSet和contains方法也很方便。这里不多展开，后面我会专门写一个用C++ set求解的版本。

2.3 为什么我建议新手先盯死暴力法

很多人一上来就追求“最优雅的解法”，这种心态我能理解，但在刷基础题时反而容易本末倒置。暴力法虽然慢，但它的逻辑链最短、最容易验证正确性，也最适合用来理解“标志位”这种数组题的核心技巧。**你先把暴力写对了，再去优化效率，这个顺序比一上来硬啃双指针要舒服得多。**何况在课程作业和大多数入门评测平台上，数据量根本到不了需要桶排序或哈希表的规模。

而且暴力法里提炼出来的检测逻辑——逐个元素去对方数组里“找”，找到就打标志位——这套思维在后续学二维数组、字符串匹配、甚至图的邻接矩阵遍历时都会反复用到。

3. 核心拆解：从“找元素”到“去重输出”的三道关卡

3.1 第一关：怎么判断“在不在另一个数组里”

最直观的做法是：遍历数组B，逐一对比当前A的元素。如果发现相等，那么说明这个元素在B中出现过，就标记为“共有”，不再继续找；如果整个B数组都扫完了，仍然没找到对应的值，就说明它不是共有元素。

判断部分的伪代码逻辑大致是这样：

for i in 0..n1-1: inB = 0 for j in 0..n2-1: if a[i] == b[j]: inB = 1 break if inB == 0: // a[i] 只出现在A中

这里的inB就是一个标志位，初始为0（假），找到后置为1（真）。很多人在这个简单环节上出错，倒不是不会写，而是忘了break。一旦忘了break，其实结果也正确，只是白白浪费了后面的循环时间；真正的问题出在后面：如果你没有标志位，而是直接在循环里printf，那遇到数组里有重复元素的情况，立刻输出多遍。

我的建议是：用标志位，不要用“找到就输出”这种投机写法。原因有两个：一是你需要在完全判定完毕后才决定是否加入结果；二是如果改成“找到就输出”，去重会很麻烦。

3.2 第二关：重复元素怎么处理才不会输出两遍

假设数组A = {2, 5, 5, 1}，数组B = {3, 4}。其中5出现了两次，而且5不在B中。如果按照直接输出的思路，两次遍历到5时都会输出，最终结果就会变成“2 5 5 1”，这明显不对。

正确的做法是：把符合条件的结果先存进一个result数组里，每次加入之前先检查result中是否已经有相同的数。如果已经有过了，就不再加入。这就是一个“输出前去重”的流程。

我用代码片段来说明去重的核心逻辑：

int existed = 0; for (int k = 0; k < count; k++) { if (result[k] == a[i]) { existed = 1; break; } } if (!existed) { result[count++] = a[i]; }

在把a[i]塞进result之前，先看result现有元素里有没有它。没有才加入，有就跳过。这段代码的代价是O(count)，但count最多不超过n1 + n2，整体还是可以接受的。

3.3 第三关：顺序和格式，这类题的隐藏得分点

顺序问题我也看到很多人纠结：输出的顺序到底按什么来？通常情况下，先输出只在A中出现的元素（按它们在A中的出现顺序），再输出只在B中出现的元素（按它们在B中的出现顺序），最后用空格分隔，末尾无多余空格。

空格的处理其实是最容易忽视的“隐藏扣分点”。很多评测系统要求元素之间以空格分隔，最后一个元素后面不能有空格。最省事的处理办法是：

for (int i = 0; i < count; i++) { if (i > 0) { printf(" "); } printf("%d", result[i]); } printf("\n");

这样第一个数前面没有空格，后面的数前面都会自动补一个空格，最后的换行也补上。不用自己去判断“是不是最后一个”。

4. 代码实现：C语言参考解法与逐行解释

4.1 完整参考代码

我先给出一版能直接跑的完整代码。题目数据量不大，数组按常见的20个长度预留足够，我习惯开得稍微大一点，避免越界。

#include <stdio.h> int main() { int n1, n2; int a[25], b[25]; int result[50]; int count = 0; scanf("%d", &n1); for (int i = 0; i < n1; i++) { scanf("%d", &a[i]); } scanf("%d", &n2); for (int i = 0; i < n2; i++) { scanf("%d", &b[i]); } // 找只在A中出现的元素 for (int i = 0; i < n1; i++) { int inB = 0; for (int j = 0; j < n2; j++) { if (a[i] == b[j]) { inB = 1; break; } } if (!inB) { int existed = 0; for (int k = 0; k < count; k++) { if (result[k] == a[i]) { existed = 1; break; } } if (!existed) { result[count++] = a[i]; } } } // 找只在B中出现的元素 for (int i = 0; i < n2; i++) { int inA = 0; for (int j = 0; j < n1; j++) { if (b[i] == a[j]) { inA = 1; break; } } if (!inA) { int existed = 0; for (int k = 0; k < count; k++) { if (result[k] == b[i]) { existed = 1; break; } } if (!existed) { result[count++] = b[i]; } } } // 按格式输出 for (int i = 0; i < count; i++) { if (i > 0) { printf(" "); } printf("%d", result[i]); } printf("\n"); return 0; }

4.2 代码执行流程的完整模拟

我拿一组测试数据演示一遍：

• 数组A：{1, 2, 3, 4}
• 数组B：{3, 4, 5, 6}

第一轮循环只对A做判断：

• 1不在B中，加入result，count变为1
• 2不在B中，加入result，count变为2
• 3在B中出现，跳过
• 4在B中出现，跳过

第二轮循环只对B做判断：

• 3在A中出现，跳过
• 4在A中出现，跳过
• 5不在A中，检查result中无5，加入，count变为3
• 6不在A中，检查result中无6，加入，count变为4

最终输出：1 2 5 6。测试下来完全符合预期。

再看一个有重复元素的例子：

• 数组A：{2, 5, 5, 1}
• 数组B：{3, 4}

A循环里：

• 2不在B中，加入result
• 第一个5不在B中，加入result
• 第二个5不在B中，但result中已有5，所以不重复加入
• 1不在B中，加入result

B循环里：

• 3不在A中，加入result
• 4不在A中，加入result

最终输出：2 5 1 3 4。这个结果既保留了出现顺序，又完成了去重。

4.3 C++版、Java版和Python版参考实现

C语言写多了之后，我经常用C++的set来快速验证思路。C++标准库里的set会自动去重，配合set_difference或者自定义判断都比较方便。这里给出一个最易读的set版本：

#include <iostream> #include <set> #include <vector> using namespace std; int main() { int n1, n2; cin >> n1; vector<int> a(n1); for (int i = 0; i < n1; i++) cin >> a[i]; cin >> n2; vector<int> b(n2); for (int i = 0; i < n2; i++) cin >> b[i]; set<int> sa(a.begin(), a.end()); set<int> sb(b.begin(), b.end()); vector<int> result; for (int x : a) { if (!sb.count(x) && find(result.begin(), result.end(), x) == result.end()) { result.push_back(x); } } for (int x : b) { if (!sa.count(x) && find(result.begin(), result.end(), x) == result.end()) { result.push_back(x); } } for (int i = 0; i < result.size(); i++) { if (i > 0) cout << " "; cout << result[i]; } cout << endl; return 0; }

Java版本用HashSet天然去重，核心思路一样：

import java.util.*; public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int n1 = sc.nextInt(); int[] a = new int[n1]; for (int i = 0; i < n1; i++) a[i] = sc.nextInt(); int n2 = sc.nextInt(); int[] b = new int[n2]; for (int i = 0; i < n2; i++) b[i] = sc.nextInt(); Set<Integer> setA = new HashSet<>(); for (int x : a) setA.add(x); Set<Integer> setB = new HashSet<>(); for (int x : b) setB.add(x); List<Integer> result = new ArrayList<>(); for (int x : a) { if (!setB.contains(x) && !result.contains(x)) result.add(x); } for (int x : b) { if (!setA.contains(x) && !result.contains(x)) result.add(x); } for (int i = 0; i < result.size(); i++) { if (i > 0) System.out.print(" "); System.out.print(result.get(i)); } System.out.println(); } }

Python的写法最短，如果你是拿Python练手，可以直接用set的对称差运算，但要注意题目对顺序的要求，set是无序的，所以最好还是手动遍历：

n1 = int(input()) a = list(map(int, input().split())) n2 = int(input()) b = list(map(int, input().split())) sa = set(a) sb = set(b) result = [] for x in a: if x not in sb and x not in result: result.append(x) for x in b: if x not in sa and x not in result: result.append(x) print(" ".join(map(str, result)))

Python的列表in判断也是O(len(result))，但数据量不大，完全够用。

5. 常见问题与排查技巧：我在实际练习中踩过的坑

5.1 日常评测中最高频的WA原因汇总

这里我把常见的错误原因列成一张表，都是实际碰到的、或者帮别人调代码时见过的：

5.2 一个非常隐蔽的坑：结果数组的大小

很多人会问，result开多大合适？最简单的判断标准是：最坏情况下所有元素都只属于一边，那么result最多有n1 + n2个元素。比如A和B完全没有交集，A中5个元素，B中5个元素，结果数组就得放得下10个。我习惯按10个预留多一点，比如开N+M再加5个余量，避免数据边界时越界。

还有一点要啰嗦一下，如果题目要求多次输入多组测试数据，记得在每组数据开始前重置result的count为0，不然上一组的结果会残留到下一组。

5.3 调试技巧：把“看不到的过程”打印出来

我调试这类数组题时有个习惯，不太直接看最终结果对不对，而是先打印中间状态。比如在每轮判断结束之后，临时加一行：

printf("当前判断 a[%d] = %d, inB = %d\n", i, a[i], inB);

这样做的好处是，你能清楚看到哪些元素被判定为共有、哪些被判定为非共有，而不是面对一个黑盒输出瞎猜。调通之后再把这些printf注释掉或者删掉即可。类似的调试手段在以后刷更复杂的题时同样有效，算是受益终身的习惯。

另外提一个标志位的进阶用法：如果数据范围有限（比如数组元素都是不超过100的正整数），可以将一个布尔数组hash[105]初始化为0，把B中所有元素标记为1，再遍历A时直接判断hash[a[i]]是否为0。这一步把内层循环O(N*M)直接降到O(N+M)，是很多题目标准答案的解法。但要注意负数情况和数据范围超出数组下标范围的情况，遇到就要换思路。

6. 再进一步：排序后双指针法的完整实现

6.1 双指针的核心思路

如果数组规模到了上万级别，暴力法就撑不住了。这时候排序后双指针是更优的选择。

思路分三步：

1. 将数组A和B分别排序；
2. 用两个指针i和j分别指向A、B的头部；
3. 比较a[i]和b[j]的大小，小者必然不可能在另一个数组中出现（因为两个数组都已排序，当前元素比对方的当前元素小，而对方后面的元素只会更大），直接输出并移动指针；相等则说明共有，两个指针同时后移。

但这里同样要去重。比较好的办法是，每次移动指针时，跳过后面所有相同的元素，确保每个值只处理一次。

6.2 参考代码

#include <stdio.h> #include <stdlib.h> int cmp(const void* p1, const void* p2) { return (*(int*)p1 - *(int*)p2); } int main() { int n1, n2; int a[100005], b[100005]; int result[200010]; int count = 0; scanf("%d", &n1); for (int i = 0; i < n1; i++) scanf("%d", &a[i]); scanf("%d", &n2); for (int i = 0; i < n2; i++) scanf("%d", &b[i]); qsort(a, n1, sizeof(int), cmp); qsort(b, n2, sizeof(int), cmp); int i = 0, j = 0; while (i < n1 && j < n2) { if (a[i] == b[j]) { i++; j++; // 跳过重复元素 while (i < n1 && a[i] == a[i - 1]) i++; while (j < n2 && b[j] == b[j - 1]) j++; } else if (a[i] < b[j]) { result[count++] = a[i]; i++; while (i < n1 && a[i] == a[i - 1]) i++; } else { result[count++] = b[j]; j++; while (j < n2 && b[j] == b[j - 1]) j++; } } // 处理剩余元素 while (i < n1) { result[count++] = a[i]; i++; while (i < n1 && a[i] == a[i - 1]) i++; } while (j < n2) { result[count++] = b[j]; j++; while (j < n2 && b[j] == b[j - 1]) j++; } for (int k = 0; k < count; k++) { if (k > 0) printf(" "); printf("%d", result[k]); } printf("\n"); return 0; }

这段代码里最需要注意的是while跳过重复元素的写法。因为排序之后重复元素会聚在一起，while (a[i] == a[i-1]) i++这一句能保证同一数值只被处理一次。如果漏掉这个，输出照样会有重复数。

从实际应用角度说，双指针法的效率提升非常明显。一万个元素的数组，暴力法最多需要一亿次比较，而排序加双指针只需要几万次比较加上排序的开销，在评测系统里就是时间超时的区别。

7. 哈希表解法：从“查找”到“直接命中”

7.1 为什么哈希表能做到O(N+M)

暴力法的痛点在于每次判断一个元素是否存在，都要遍历另一个数组。哈希表专门解决这个问题：通过哈希函数把元素映射到某个存储位置，查询时直接根据哈希值定位，平均时间复杂度是O(1)。

如果数据元素是整数且范围不大，甚至不用真正的哈希表，用一个数组模拟“桶”就行。比如题目约定元素在0到100之间，就开一个int bucket[101]，初始为0，遍历B时bucket[b[i]] = 1，后面检查a[i]是否存在时直接看bucket[a[i]]。这就是桶的思想，也叫计数数组。

7.2 C++哈希表版本

C++里用unordered_set直接搞定：

#include <iostream> #include <unordered_set> #include <vector> using namespace std; int main() { int n1, n2; cin >> n1; vector<int> a(n1); for (int i = 0; i < n1; i++) cin >> a[i]; cin >> n2; vector<int> b(n2); for (int i = 0; i < n2; i++) cin >> b[i]; unordered_set<int> sa(a.begin(), a.end()); unordered_set<int> sb(b.begin(), b.end()); vector<int> result; for (int x : a) { if (!sb.count(x)) { result.push_back(x); } } for (int x : b) { if (!sa.count(x)) { result.push_back(x); } } for (int i = 0; i < result.size(); i++) { if (i > 0) cout << " "; cout << result[i]; } cout << endl; return 0; }

这个版本和C语言版相比，去重逻辑极其省事：unordered_set本身就不允许重复值，所以遍历原始数组时一个值只会被放进result一次。去掉了我之前在result里反复查找的步骤。

哈希方法在处理大范围随机整数时非常可靠。我给一个在本地机器上跑过的对比数据：两个数组各5000个随机整数，暴力法耗时大约24毫秒，哈希表版本耗时不到1毫秒。虽然基础题用暴力法不会超时，但提前知道这个差距，对后面学习数据结构和算法设计会有更直观的感受。

8. 边界情况与扩展思考：这道题还能怎么变

8.1 极端边界条件的处理

做题不能只盯着正常样例，还得想边界。比如：

• 一个数组为空：那么整个另一个数组中的所有元素都是非共有元素，输出整个非空数组且去重。
• 两个数组完全相同：输出结果应为空，也就是只输出一个回车。
• 两个数组完全没有交集：输出两个数组合并后的去重结果。
• 数组中存在负数：桶数组无法直接处理负数下标，需要偏移或者改用哈希表。
• 元素值极大或极小，比如超过int范围：要考虑用long long，或者统一哈希方案。

我在写代码时有一个习惯：本地测试永远加三组特殊数据，一组空数组，一组全部重复，一组完全无交集。这三组数据能拦截掉绝大部分隐藏bug。

8.2 从数组到集合的思维升级

如果把这道题抽象成集合运算，它其实就是“对称差”。集合论里，A和B的对称差可以写作(A - B) ∪ (B - A)，也就是“两边的差集的并集”。一旦你把这个思路理清楚，很多复杂问题就有了统一的分析框架：比如数据库里比较两个表的数据差异、生产环境对比两个配置文件的不同项、甚至版本对比工具里找出改动过的文件，底层都是对称差的思维。

我当初在练习题里碰到它的时候，并没有意识到它会在后面的工作里以各种形态出现。后来做数据同步、写脚本比对两个文件夹时，才发现当年那道朴素的数组题，练的就是“找出差异”这种基础能力。

8.3 如果让你扩展这道题，你会怎么改

好的练习题往往能引出更多的思考方向。如果我把这道题稍微改一下，变成“找出两个数组中共同出现的所有元素”，解法是不是完全一样？对，核心思路就是把判断条件反转一下。如果再改成“找出A中有而B中没有的元素”，那就只需要保留前半段逻辑。原理完全一致，只是输出条件变了一处。

再扩展一步，如果输入不是两段数组而是两段文本文件，要根据某列主键找出缺失记录，本质方法也是一样的。数组只是最基础的存储形式，核心方法——标志位、哈希表、排序——这些思想才是真正能迁移到各种场景的东西。

9. 写在后面的个人经验

我自己的体会是：数组题看起来人人都会，但真正能一次写对的人不多。不是大家不会写for循环，而是缺少“把所有情况都考虑清楚”的习惯。标志位怎么打、重复元素怎么处理、空格怎么控制、边界怎么兜底，这些都是刷题过程中需要反复打磨的细节。

如果你现在正卡在这道题上，别急。先把暴力法写出来，再用特殊样例验证一遍，然后试着改成哈希表或者双指针。一次不行就两次，跑通了以后你会觉得，数组这个基础反而成了最可靠的工具。等以后碰到底层算法、系统设计里的数据比对场景时，你可能会像我一样，突然想起很多年前那道朴素又琐碎的数组题，然后感叹一句：原来那些年练的基本功，从来没有白费。