Java 实例 – 数组交集（千字长文）

Java 实例 – 数组交集：从入门到实战

在日常开发中，我们经常会遇到需要找出两个数组中共同元素的场景。比如，用户 A 和用户 B 的好友列表中，有哪些是共同的好友？又比如，两个商品库存列表中，哪些商品是重叠的？这类问题本质上就是“数组交集”问题。

Java 实例 – 数组交集 是一个非常典型的算法应用场景，它不仅考验你对数组操作的理解，也涉及集合、循环、去重等多个核心知识点。今天，我们就来一步步拆解这个问题，用真实代码带你掌握它的多种实现方式。

什么是数组交集？

在数学中，两个集合的交集指的是同时属于这两个集合的元素。在 Java 中，数组虽然不是集合（Collection），但我们可以把它们当作“有序的元素列表”来处理。

举个例子：

int[] arr1 = {1, 2, 3, 4, 5};
int[] arr2 = {3, 4, 5, 6, 7};

这两个数组的交集就是 {3, 4, 5}，因为只有这三个数字同时出现在两个数组中。

📌 小贴士：交集的元素顺序不重要，但通常我们按原数组顺序或排序后输出。

创建数组与初始化

在开始计算交集前，我们需要先创建并初始化两个数组。Java 中数组是固定长度的容器，一旦创建就不能改变长度，但可以修改其中的元素。

// 创建两个整型数组
int[] array1 = {1, 2, 3, 4, 5};
int[] array2 = {3, 4, 5, 6, 7};

// 也可以使用 new 关键字手动创建
int[] array3 = new int[5];
array3[0] = 10;
array3[1] = 20;
array3[2] = 30;
array3[3] = 40;
array3[4] = 50;

✅ 注意：数组索引从 0 开始，array3[4] 是最后一个元素。

在实际项目中，我们可能从用户输入、文件读取或数据库查询中获取数据，然后转为数组。但今天为了聚焦核心逻辑，我们直接使用静态数据进行演示。

方法一：暴力遍历法（双重循环）

这是最直观、最容易理解的方法。它的思路是：遍历第一个数组的每一个元素，再遍历第二个数组，检查是否相等。

public static int[] findIntersection(int[] arr1, int[] arr2) {
    // 用于存储结果的临时数组，初始长度设为较小数组的长度
    int[] result = new int[Math.min(arr1.length, arr2.length)];
    int index = 0; // 记录结果数组当前填充位置

    // 外层循环：遍历第一个数组
    for (int i = 0; i < arr1.length; i++) {
        // 内层循环：遍历第二个数组
        for (int j = 0; j < arr2.length; j++) {
            // 如果两个元素相等，说明是交集元素
            if (arr1[i] == arr2[j]) {
                // 避免重复添加（重要！）
                boolean isDuplicate = false;
                for (int k = 0; k < index; k++) {
                    if (result[k] == arr1[i]) {
                        isDuplicate = true;
                        break;
                    }
                }
                // 如果不是重复元素，就加入结果
                if (!isDuplicate) {
                    result[index++] = arr1[i];
                }
            }
        }
    }

    // 将结果数组裁剪到实际长度，避免多余 0 值
    int[] finalResult = new int[index];
    for (int i = 0; i < index; i++) {
        finalResult[i] = result[i];
    }

    return finalResult;
}

🔍 关键点说明：

• 使用 index 来跟踪结果数组的写入位置。
• Math.min(arr1.length, arr2.length) 是一个合理的预估上限，但最终长度可能更小。
• 去重逻辑非常关键，否则会出现 [3, 4, 5, 3, 4, 5] 这样的错误结果。
• 时间复杂度为 O(n × m × k)，其中 n、m 是数组长度，k 是去重检查的平均次数。

这个方法虽然效率不高，但逻辑清晰，特别适合初学者理解“交集”是怎么一步步找出来的。

方法二：使用 HashSet 提升效率

当数组较大时，暴力法会变得非常慢。这时我们可以借助 HashSet 的快速查找特性来优化。

HashSet 是基于哈希表实现的集合，它可以在 O(1) 时间内判断某个元素是否存在。

import java.util.HashSet;
import java.util.Set;

public static int[] findIntersectionOptimized(int[] arr1, int[] arr2) {
    // 将第二个数组的元素放入 HashSet，便于快速查找
    Set<Integer> set = new HashSet<>();
    for (int num : arr2) {
        set.add(num);
    }

    // 用于存储结果的集合（自动去重）
    Set<Integer> resultSet = new HashSet<>();

    // 遍历第一个数组，检查每个元素是否在 set 中
    for (int num : arr1) {
        if (set.contains(num)) {
            resultSet.add(num); // 自动去重
        }
    }

    // 将 Set 转回数组
    int[] result = new int[resultSet.size()];
    int index = 0;
    for (int num : resultSet) {
        result[index++] = num;
    }

    return result;
}

✅ 优势分析：

• 时间复杂度优化为 O(n + m)，远快于暴力法。
• 代码更简洁，去重由 HashSet 自动处理。
• 适用于数据量较大的场景，比如处理用户标签、商品 ID 等。

💡 比喻：把 arr2 的元素放进一个“快速查找柜子”（HashSet），然后逐个检查 arr1 的元素是否在这个柜子里。如果在，就记下来。

方法三：排序 + 双指针法（适用于已排序数组）

如果两个数组本身是有序的，我们可以使用“双指针”技巧，进一步优化空间和时间。

import java.util.Arrays;

public static int[] findIntersectionSorted(int[] arr1, int[] arr2) {
    // 先排序（如果原数组未排序）
    Arrays.sort(arr1);
    Arrays.sort(arr2);

    int i = 0, j = 0; // 双指针
    int[] result = new int[Math.min(arr1.length, arr2.length)];
    int index = 0;

    while (i < arr1.length && j < arr2.length) {
        if (arr1[i] == arr2[j]) {
            // 避免重复添加
            if (index == 0 || result[index - 1] != arr1[i]) {
                result[index++] = arr1[i];
            }
            i++;
            j++;
        } else if (arr1[i] < arr2[j]) {
            i++; // arr1 当前元素太小，移动 i
        } else {
            j++; // arr2 当前元素太小，移动 j
        }
    }

    // 裁剪数组
    return Arrays.copyOf(result, index);
}

📌 运行逻辑：

• 两个指针分别指向两个数组的开头。
• 如果元素相等，加入结果并同时移动两个指针。
• 如果 arr1[i] < arr2[j]，说明 arr1 的值太小，只能移动 i。
• 反之移动 j。

✅ 优势：

• 空间复杂度为 O(1)（不考虑结果数组）。
• 无需额外集合，适合内存受限环境。
• 适合已排序数据，如数据库查询结果。

实际案例：好友共同关注列表

假设我们有两个用户的好友列表：

int[] user1Friends = {101, 203, 305, 407, 509};
int[] user2Friends = {305, 407, 601, 702, 803};

我们想找出他们共同关注的人：

int[] commonFriends = findIntersectionOptimized(user1Friends, user2Friends);
System.out.println("共同好友 ID：" + Arrays.toString(commonFriends));
// 输出：共同好友 ID：[305, 407]

这个逻辑可以直接用于社交平台、推荐系统、权限匹配等场景。

性能对比表

✅ 推荐：除非数据已排序或内存极受限，否则优先使用 HashSet 法。

总结与建议

Java 实例 – 数组交集 并不是一个孤立的问题，它背后蕴含着算法设计的通用思想：如何在效率与可读性之间找到平衡。

• 初学者建议从暴力法入手，理解“交集”本质；
• 中级开发者应掌握 HashSet 优化方案，提升代码性能；
• 高级场景可考虑双指针或并行计算（如 parallelStream）。

最后提醒一点：不要盲目追求最优解，先写对，再写快。尤其是在面试或项目初期，清晰的代码比“理论上更快”的代码更有价值。

如果你在项目中遇到类似需求，不妨先用 HashSet 实现，再根据性能表现决定是否优化。

记住，每一个算法的背后，都是对问题本质的拆解与重构。多动手、多思考，你的 Java 技能一定会稳稳提升。