Java数组交集：从基础到高效优化的完整指南289

在日常编程和算法面试中，查找两个或多个集合（如数组）的交集是一个非常常见的问题。尤其是在处理大量数据时，如何“快速”地找到交集，成为了衡量代码效率的关键。本文将作为一名专业的程序员，深入探讨Java中实现数组交集的不同方法，从最直观的暴力解法到利用高级数据结构和算法进行性能优化的方案，并着重分析它们的时间和空间复杂度，帮助你选择最适合特定场景的策略。

什么是数组交集？

数组交集指的是两个或多个数组中都存在的共同元素组成的集合。例如，给定数组 `A = [1, 2, 3, 4, 5]` 和 `B = [3, 4, 5, 6, 7]`，它们的交集就是 `[3, 4, 5]`。

在实际应用中，交集操作广泛应用于数据库查询、数据去重、推荐系统（查找共同兴趣）以及许多算法问题中。

1. 暴力解法 (Brute Force)

这是最直接也最容易理解的方法。我们使用两层嵌套循环，将第一个数组中的每个元素与第二个数组中的所有元素进行比较。如果找到匹配项，就将其添加到结果集中。

实现思路

创建一个空的 `List` 或 `Set` 来存储交集结果。
遍历第一个数组 `arr1`。
在内部循环中，遍历第二个数组 `arr2`。
如果 `arr1[i]` 等于 `arr2[j]`，则将该元素添加到结果集中。为了避免重复添加，可以在添加前检查结果集中是否已存在该元素。

Java 代码示例

import ;
import ;
public class ArrayIntersectionBruteForce {
public static List<Integer> findIntersection(int[] arr1, int[] arr2) {
List<Integer> intersection = new ArrayList<>();
for (int i = 0; i < ; i++) {
for (int j = 0; j < ; j++) {
if (arr1[i] == arr2[j]) {
// 确保不添加重复元素
if (!(arr1[i])) {
(arr1[i]);
}
// 如果我们只关心不重复的交集，可以在找到匹配后直接跳出内层循环
// 但如果arr1中有重复元素，且arr2中也对应有，这个逻辑可能不满足所有需求
// 例如 arr1 = [1,1,2], arr2 = [1,2], 交集通常是 [1,2]
// 如果是需要计数，则需要更复杂的逻辑
break; // 找到一个匹配后，arr1[i]已处理，不再需要与arr2的剩余元素比较
}
}
}
return intersection;
}
public static void main(String[] args) {
int[] arr1 = {1, 2, 3, 4, 5};
int[] arr2 = {3, 4, 5, 6, 7};
List<Integer> result = findIntersection(arr1, arr2);
("暴力解法交集: " + result); // 输出: [3, 4, 5]
int[] arr3 = {1, 1, 2, 2, 3};
int[] arr4 = {1, 2, 2, 4};
List<Integer> result2 = findIntersection(arr3, arr4);
("暴力解法交集 (含重复元素): " + result2); // 输出: [1, 2, 3]
}
}

复杂度分析

时间复杂度： O(m * n)，其中 m 和 n 分别是两个数组的长度。这是因为存在嵌套循环。如果 `()` 每次都需要遍历 `intersection` 列表，那么最坏情况下会达到 O(m * n * k)，k 是交集大小。
空间复杂度： O(k)，其中 k 是交集的大小。用于存储结果。

这种方法虽然简单，但对于大型数组来说效率非常低下，不建议在生产环境中使用。

2. 利用 Java 集合框架 - `()`

Java 集合框架提供了强大的工具来处理集合操作。`List` 接口有一个 `retainAll(Collection<?> c)` 方法，它会从当前列表中移除所有不在指定集合 `c` 中的元素，从而达到计算交集的目的。

实现思路

将两个数组分别转换为 `List`。
在一个 `List` 上调用 `retainAll()` 方法，传入另一个 `List` 作为参数。

Java 代码示例

import ;
import ;
import ;
public class ArrayIntersectionRetainAll {
public static List<Integer> findIntersection(int[] arr1, int[] arr2) {
// 将基本类型数组转换为List<Integer>
List<Integer> list1 = new ArrayList<>();
for (int num : arr1) {
(num);
}
List<Integer> list2 = new ArrayList<>();
for (int num : arr2) {
(num);
}
// 使用retainAll方法
(list2); // list1现在包含交集元素
return list1;
}
// 如果希望结果是无重复的交集
public static List<Integer> findUniqueIntersection(int[] arr1, int[] arr2) {
List<Integer> list1 = new ArrayList<>();
for (int num : arr1) {
(num);
}
List<Integer> list2 = new ArrayList<>();
for (int num : arr2) {
(num);
}
(list2);
// 为了确保结果的唯一性，可以将其转换为HashSet再转回ArrayList
return new ArrayList<>(new <>(list1));
}
public static void main(String[] args) {
int[] arr1 = {1, 2, 3, 4, 5};
int[] arr2 = {3, 4, 5, 6, 7};
List<Integer> result = findIntersection(arr1, arr2);
("retainAll 解法交集: " + result); // 输出: [3, 4, 5]
int[] arr3 = {1, 1, 2, 2, 3};
int[] arr4 = {1, 2, 2, 4};
List<Integer> result2 = findIntersection(arr3, arr4);
("retainAll 解法交集 (含重复元素): " + result2); // 输出: [1, 2, 2, 3] (注意重复元素保留)
List<Integer> uniqueResult2 = findUniqueIntersection(arr3, arr4);
("retainAll 解法交集 (去重): " + uniqueResult2); // 输出: [1, 2, 3]
}
}

复杂度分析

时间复杂度： `retainAll()` 方法的实现通常涉及到遍历调用方列表中的每个元素，并检查该元素是否存在于参数集合中。如果参数集合是一个 `ArrayList`，则检查会是 O(n) 操作，导致总时间复杂度在最坏情况下仍接近 O(m * n)。然而，如果参数集合是一个 `HashSet`（或内部优化为 `HashSet`），查找效率会大大提高。Java 8+ 的 `()` 会在内部将参数集合转换为 `HashSet` 以优化性能，因此其平均时间复杂度趋近于 O(m + n)。
空间复杂度： O(m + n)，用于创建两个 `ArrayList`。如果内部创建 `HashSet`，还需要额外的 O(min(m, n)) 空间。

这种方法代码简洁，但在底层性能上，它与下面要介绍的 `HashSet` 方法有相似之处，但通常会因为额外的 `List` 创建和转换而稍逊一筹。

3. 基于 `HashSet` 的高效解法 (推荐用于无序数组)

这是最常用且效率最高的通用方法之一，尤其适用于数组无序的情况。`HashSet` 提供了 O(1) 平均时间复杂度的查找操作，这使得交集计算变得非常迅速。

实现思路

将第一个（或较小的一个）数组的所有元素添加到 `HashSet` 中。这将利用 `HashSet` 快速查找的特性。
遍历第二个数组。对于第二个数组中的每个元素，检查它是否存在于 `HashSet` 中。
如果存在，则说明该元素是交集的一部分，将其添加到结果集中。为了避免结果集中的重复，结果集也可以是一个 `HashSet`，或者在添加前检查。

Java 代码示例

import ;
import ;
import ;
import ;
public class ArrayIntersectionHashSet {
/
* 查找两个数组的唯一交集（结果不含重复元素）
*
* @param arr1 数组1
* @param arr2 数组2
* @return 包含交集元素的列表
*/
public static List<Integer> findIntersection(int[] arr1, int[] arr2) {
Set<Integer> set1 = new HashSet<>();
for (int num : arr1) {
(num);
}
List<Integer> intersection = new ArrayList<>();
for (int num : arr2) {
if ((num)) {
// 如果set1中包含该元素，并且结果列表中尚未添加，则添加
// 仅适用于结果列表不是HashSet的情况
if (!(num)) { // 避免结果列表出现重复
(num);
}
// 如果我们允许结果列表有重复，比如 {1,1,2} 和 {1,2,2} -> {1,2,2}，需要更复杂的逻辑
}
}
return intersection;
}
/
* 查找两个数组的交集，保留重复元素（例如：[1,1,2] 和 [1,2,2] -> [1,2]）
* 这个问题更复杂，需要考虑每个元素出现的次数。
* 这里的实现是保留在两个数组中都至少出现一次的元素，且只添加一次到结果中。
* 如果希望保留最小出现次数，见下面的方法。
*/
public static List<Integer> findIntersectionWithMinDuplicates(int[] arr1, int[] arr2) {
// 使用一个HashSet来存储arr1中的元素，便于快速查找
Set<Integer> set = new HashSet<>();
for (int num : arr1) {
(num);
}
// 使用一个List来存储结果
List<Integer> intersection = new ArrayList<>();
// 使用另一个HashSet来确保添加到结果列表中的元素是唯一的
Set<Integer> addedToResult = new HashSet<>();
for (int num : arr2) {
if ((num) && (num)) { // 如果set包含该元素且结果中尚未添加
(num);
}
}
return intersection;
}
/
* 查找交集，其中每个元素出现的次数为它在两个数组中出现次数的最小值
* 例如：arr1 = [1,1,2,3], arr2 = [1,2,2,4] -> intersection = [1,2]
*/
public static List<Integer> findIntersectionWithFrequency(int[] arr1, int[] arr2) {
<Integer, Integer> map = new <>();
for (int num : arr1) {
(num, (num, 0) + 1);
}
List<Integer> intersection = new ArrayList<>();
for (int num : arr2) {
if ((num) && (num) > 0) {
(num);
(num, (num) - 1); // 找到一个匹配后，减少计数
}
}
return intersection;
}

public static void main(String[] args) {
int[] arr1 = {1, 2, 3, 4, 5};
int[] arr2 = {3, 4, 5, 6, 7};
List<Integer> result = findIntersection(arr1, arr2);
("HashSet 解法唯一交集: " + result); // 输出: [3, 4, 5]
int[] arr3 = {1, 1, 2, 2, 3};
int[] arr4 = {1, 2, 2, 4};
List<Integer> resultWithDuplicates = findIntersectionWithFrequency(arr3, arr4);
("HashSet 解法交集 (按最小频率): " + resultWithDuplicates); // 输出: [1, 2, 2]
}
}

复杂度分析

时间复杂度： O(m + n)。首先，将第一个数组的 m 个元素添加到 `HashSet` 中需要 O(m) 的平均时间。然后，遍历第二个数组的 n 个元素，每次查找操作平均为 O(1)。因此总时间复杂度是 O(m + n)。
空间复杂度： O(min(m, n))。`HashSet` 存储了第一个数组的所有元素，因此空间占用取决于较小数组的长度。结果集还需要 O(k) 空间。

这是在大多数情况下，处理无序数组交集问题的首选方法，因为它在时间和空间效率之间取得了很好的平衡。

4. 排序 + 双指针法 (推荐用于有序数组或需要频繁交集操作)

如果两个数组已经有序，或者在进行多次交集操作前可以预先排序，那么双指针法是一种非常高效的解决方案，它不需要额外的哈希表空间。

实现思路

首先，对两个数组进行排序。如果它们已经有序，则跳过此步。
使用两个指针 `p1` 和 `p2`，分别指向两个数组的起始位置。
比较 `arr1[p1]` 和 `arr2[p2]`：

如果 `arr1[p1] == arr2[p2]`，说明找到了一个共同元素。将其添加到结果集中，并同时移动 `p1` 和 `p2` 到下一个位置。为了避免结果中的重复，可以检查上一个添加的元素是否相同。
如果 `arr1[p1] < arr2[p2]`，说明 `arr1[p1]` 太小，不可能与 `arr2[p2]` 及其后面的元素匹配（因为 `arr2` 是有序的）。所以移动 `p1` 到下一个位置。
如果 `arr1[p1] > arr2[p2]`，同理，移动 `p2` 到下一个位置。


重复上述过程，直到任一指针超出数组边界。

Java 代码示例

import ;
import ;
import ;
public class ArrayIntersectionTwoPointers {
/
* 查找两个数组的唯一交集（结果不含重复元素）
*
* @param arr1 数组1
* @param arr2 数组2
* @return 包含交集元素的列表
*/
public static List<Integer> findIntersection(int[] arr1, int[] arr2) {
// 1. 排序两个数组
(arr1);
(arr2);
List<Integer> intersection = new ArrayList<>();
int p1 = 0; // 指向 arr1
int p2 = 0; // 指向 arr2
while (p1 < && p2 < ) {
if (arr1[p1] == arr2[p2]) {
// 找到共同元素
// 确保不添加重复元素到结果中
if (() || (() - 1) != arr1[p1]) {
(arr1[p1]);
}
p1++;
p2++;
} else if (arr1[p1] < arr2[p2]) {
p1++; // arr1[p1] 太小，移动 p1
} else { // arr1[p1] > arr2[p2]
p2++; // arr2[p2] 太小，移动 p2
}
}
return intersection;
}
/
* 查找交集，其中每个元素出现的次数为它在两个数组中出现次数的最小值
* 例如：arr1 = [1,1,2,3], arr2 = [1,2,2,4] -> intersection = [1,2]
*/
public static List<Integer> findIntersectionWithFrequency(int[] arr1, int[] arr2) {
(arr1);
(arr2);
List<Integer> intersection = new ArrayList<>();
int p1 = 0;
int p2 = 0;
while (p1 < && p2 < ) {
if (arr1[p1] == arr2[p2]) {
(arr1[p1]); // 直接添加，允许重复
p1++;
p2++;
} else if (arr1[p1] < arr2[p2]) {
p1++;
} else {
p2++;
}
}
return intersection;
}

public static void main(String[] args) {
int[] arr1 = {1, 2, 3, 4, 5};
int[] arr2 = {3, 4, 5, 6, 7};
List<Integer> result = findIntersection(arr1, arr2);
("排序+双指针解法唯一交集: " + result); // 输出: [3, 4, 5]
int[] arr3 = {1, 1, 2, 2, 3};
int[] arr4 = {1, 2, 2, 4};
List<Integer> resultWithDuplicates = findIntersectionWithFrequency(arr3, arr4);
("排序+双指针解法交集 (按最小频率): " + resultWithDuplicates); // 输出: [1, 2, 2]
}
}

复杂度分析

时间复杂度： O(m log m + n log n) 用于排序，加上 O(m + n) 用于双指针遍历。所以总时间复杂度是 O(m log m + n log n)。如果数组已经有序，则仅为 O(m + n)。
空间复杂度： O(1)（如果不考虑结果列表的存储和排序算法可能使用的额外空间，Java内置的 `` 对基本类型数组会使用改进的快速排序，空间复杂度为O(logN)或O(N)取决于具体实现）。结果列表需要 O(k) 空间。

当数组非常大且无序时，排序的开销可能会很大。但在数据已经有序，或者对内存有严格限制，或者需要对同一组数组进行多次交集操作时，这种方法非常优秀。

5. Java Stream API (现代简洁写法)

Java 8 引入的 Stream API 提供了一种函数式编程风格来处理集合操作，使代码更加简洁和富有表现力。虽然通常不会比手写循环更快，但在可读性和开发效率上具有优势。

实现思路

将其中一个数组转换为 `Set` (为了快速查找)。
将另一个数组转换为 Stream。
使用 `filter` 操作，检查 Stream 中的每个元素是否存在于 `Set` 中。
使用 `collect` 操作将过滤后的元素收集到 `List` 中。

Java 代码示例

import ;
import ;
import ;
import ;
public class ArrayIntersectionStreamAPI {
/
* 查找两个数组的唯一交集（结果不含重复元素）
*
* @param arr1 数组1
* @param arr2 数组2
* @return 包含交集元素的列表
*/
public static List<Integer> findIntersection(int[] arr1, int[] arr2) {
// 将其中一个数组转换为Set，用于O(1)查找
Set<Integer> set2 = (arr2).boxed().collect(());
// 将另一个数组转换为Stream，并过滤出存在于set2中的元素
return (arr1)
.boxed() // 将int转换为Integer对象
.filter(set2::contains) // 过滤，只保留set2中存在的元素
.distinct() // 确保结果中没有重复（如果arr1本身有重复）
.collect(()); // 收集为List
}
public static void main(String[] args) {
int[] arr1 = {1, 2, 3, 4, 5};
int[] arr2 = {3, 4, 5, 6, 7};
List<Integer> result = findIntersection(arr1, arr2);
("Stream API 解法唯一交集: " + result); // 输出: [3, 4, 5]
int[] arr3 = {1, 1, 2, 2, 3};
int[] arr4 = {1, 2, 2, 4};
List<Integer> result2 = findIntersection(arr3, arr4);
("Stream API 解法唯一交集 (含重复元素): " + result2); // 输出: [1, 2, 3]
}
}

复杂度分析

时间复杂度： O(m + n)。将 `arr2` 转换为 `Set` 需要 O(n) 时间。然后遍历 `arr1` 的 Stream 并进行 `contains` 检查，平均为 O(1) 每次，所以是 O(m)。总计 O(m + n)。由于 Stream 操作涉及自动装箱/拆箱和管道开销，实际性能可能略低于手动 `HashSet` 循环，但对于大多数应用而言，这种差异可以忽略。
空间复杂度： O(m + n)。`Set` 存储 `arr2` 的元素，`List` 存储结果。

Stream API 适用于追求代码简洁性和现代 Java 特性的场景。当对性能要求极为严苛时，手动 `HashSet` 循环可能是一个微小的优势。

选择最佳方法

选择哪种方法取决于具体的应用场景和需求：
数组规模：

小型数组（<1000）： 任何方法都可以，暴力解法甚至 `retainAll` 都不会有明显性能问题。简洁性可能是首要考虑。
中大型数组（>1000）： 强烈推荐 `HashSet` 解法 或 排序+双指针法。


数组是否已排序：

已排序： 排序+双指针法 是最佳选择，时间复杂度为 O(m + n)，且空间复杂度最低。
未排序： `HashSet` 解法 通常是最佳选择，时间复杂度为 O(m + n)，优于排序+双指针法（因为它需要额外的排序时间）。


是否允许结果中包含重复元素：

如果交集结果需要包含重复元素，并且每个元素出现的次数是它在两个数组中出现次数的最小值（例如 `[1,1,2]` 和 `[1,2,2]` 的交集是 `[1,2]`），那么你需要使用基于 `HashMap` 的计数方法（如上面 `findIntersectionWithFrequency` 所示）或者修改双指针法。
如果只需要唯一的交集元素，`HashSet` 解法配合 `distinct()` 或结果也使用 `HashSet` 会更简单。


内存限制：

如果内存非常紧张，且数组可以被排序，排序+双指针法 是首选，因为它只需要 O(1) 额外空间（不计结果集和部分排序算法的栈空间）。
`HashSet` 需要额外的 O(min(m, n)) 空间。


代码简洁性/可读性：

Stream API 和 `retainAll` 通常代码最简洁。
`HashSet` 解法在简洁性和性能之间取得了很好的平衡。

总结比较表

方法
时间复杂度 (最差/平均)
空间复杂度 (额外)
优点
缺点
适用场景




暴力解法
O(m*n)
O(k)
最简单易懂
效率极低
极小数组、教学演示


`()`
O(m+n) (优化后)
O(m+n)
代码简洁
性能略逊于 `HashSet` 手动实现，可能保留重复
中等规模，追求简洁


`HashSet` 解法
O(m+n) (平均)
O(min(m,n))
高效，通用，适用于无序数组
需要额外空间
最常用，大型无序数组


排序+双指针
O(m log m + n log n)
O(1) (取决于排序)
空间效率高，已排序数组极快
需要排序预处理，对无序大数组可能较慢
内存受限，数组已排序，或频繁交集操作


Stream API
O(m+n) (平均)
O(m+n)
代码现代简洁，函数式风格
性能可能略低于手动循环，有装箱拆箱开销
追求代码可读性和现代Java特性

在Java中实现数组交集，我们有多种方法可供选择。对于大多数通用场景，特别是处理无序数组时，基于 `HashSet` 的方法因其 O(m+n) 的平均时间复杂度和相对合理的空间开销，是性能和实现简洁性的最佳平衡点。如果你的数组已经有序，或者对内存有严格限制，那么排序加双指针法将是更优的选择。了解这些方法的底层原理和复杂度，能够帮助你根据实际需求做出明智的决策，编写出既正确又高效的Java代码。

2025-11-06

---

上一篇：Java数组的深度探索：理解其对象特性、多维结构与性能优化

下一篇：Java代码逆向工程与解密：原理、工具、实践与安全考量