当前位置：首页 > article >正文

JavaScript实现一个函数，找出两个数组的交集（共同元素）的原理及思路。

article 2025/3/26 1:45:56

大白话JavaScript实现一个函数，找出两个数组的交集（共同元素）的原理及思路。

我们的目标是用 JavaScript 写一个函数，这个函数能找出两个数组里都有的元素，也就是找出它们的交集。比如数组 [1, 2, 3] 和 [2, 3, 4]，它们的交集就是 [2, 3]。

实现思路

为了找出两个数组的交集，我们可以按照下面的步骤来做：

用一个 Set 对象来存储第一个数组里的所有元素。Set 是一种数据结构，它的特点是每个元素只能出现一次，这样我们可以快速判断某个元素是否存在。
遍历第二个数组，对于其中的每个元素，检查它是否在 Set 里。
如果某个元素在 Set 里，那就说明这个元素是两个数组的共同元素，把它添加到结果数组里。
最后返回结果数组。

代码实现

下面是实现这个功能的 JavaScript 代码，每一行都有详细的注释：

function intersection(arr1, arr2) {
    // 创建一个 Set 对象，用来存储 arr1 中的所有元素
    const set = new Set(arr1);

    // 创建一个空数组，用来存储两个数组的交集
    const result = [];

    // 遍历 arr2 数组
    for (let i = 0; i < arr2.length; i++) {
        // 检查当前元素是否存在于 Set 中
        if (set.has(arr2[i])) {
            // 如果存在，说明这个元素是两个数组的共同元素
            // 将其添加到结果数组中
            result.push(arr2[i]);
            // 为了避免重复添加相同的元素，从 Set 中删除这个元素
            set.delete(arr2[i]);
        }
    }

    // 返回结果数组
    return result;
}

// 测试函数
const array1 = [1, 2, 3, 4];
const array2 = [3, 4, 5, 6];
const commonElements = intersection(array1, array2);
console.log(commonElements); // 输出: [3, 4]

下面为你介绍另外几种找出两个数组交集的方法。

使用双重循环

思路

通过两层循环，遍历第一个数组的每个元素，再在第二个数组中检查该元素是否存在。如果存在且还未添加到结果数组中，就将其添加到结果数组。

代码示例

function intersectionWithNestedLoops(arr1, arr2) {
    // 用于存储交集元素的数组
    const result = [];
    // 外层循环遍历 arr1
    for (let i = 0; i < arr1.length; i++) {
        // 内层循环遍历 arr2
        for (let j = 0; j < arr2.length; j++) {
            // 检查 arr1 中的元素是否等于 arr2 中的元素
            if (arr1[i] === arr2[j]) {
                // 检查该元素是否已经在结果数组中
                if (!result.includes(arr1[i])) {
                    // 如果不在结果数组中，添加到结果数组
                    result.push(arr1[i]);
                }
            }
        }
    }
    return result;
}

// 测试示例
const array1 = [1, 2, 3, 4];
const array2 = [3, 4, 5, 6];
const commonElements = intersectionWithNestedLoops(array1, array2);
console.log(commonElements);

使用 `filter` 和 `includes` 方法

思路

使用 filter 方法遍历第一个数组，对于每个元素，使用 includes 方法检查它是否存在于第二个数组中。如果存在，就将该元素保留在过滤后的数组中。

代码示例

function intersectionWithFilterAndIncludes(arr1, arr2) {
    // 使用 filter 方法过滤出 arr1 中存在于 arr2 的元素
    return arr1.filter(item => arr2.includes(item));
}

// 测试示例
const array3 = [1, 2, 3, 4];
const array4 = [3, 4, 5, 6];
const commonElements2 = intersectionWithFilterAndIncludes(array3, array4);
console.log(commonElements2);

使用 `reduce` 方法

思路

使用 reduce 方法遍历第一个数组，对于每个元素，检查它是否存在于第二个数组中且不在结果数组中。如果满足条件，就将其添加到结果数组中。

代码示例

function intersectionWithReduce(arr1, arr2) {
    // 使用 reduce 方法累加符合条件的元素到结果数组
    return arr1.reduce((result, current) => {
        // 检查当前元素是否存在于 arr2 且不在结果数组中
        if (arr2.includes(current) &&!result.includes(current)) {
            // 如果满足条件，将元素添加到结果数组
            result.push(current);
        }
        return result;
    }, []);
}

// 测试示例
const array5 = [1, 2, 3, 4];
const array6 = [3, 4, 5, 6];
const commonElements3 = intersectionWithReduce(array5, array6);
console.log(commonElements3);

上述这些方法各有优劣。双重循环方法直观但效率较低，尤其是数组较大时；使用 filter 和 includes 方法代码简洁，但 includes 方法在大数据集下效率也不高；使用 Set 的方法在查找元素时效率较高，是较为推荐的做法。

这些方法之间的区别：

1. 实现原理

使用 Set 的方法
- 该方法借助 Set 数据结构的特性，Set 中的元素具有唯一性，并且查找元素的时间复杂度为 $O (1)$ 。首先将第一个数组的元素存入 Set 中，接着遍历第二个数组，检查每个元素是否存在于 Set 里，若存在则添加到结果数组。这种方式利用了 Set 的高效查找能力，避免了不必要的重复检查。
双重循环方法
- 通过两层嵌套的 for 循环来实现。外层循环遍历第一个数组的每个元素，内层循环遍历第二个数组，逐个比较元素是否相等。若相等且该元素还未添加到结果数组中，就将其添加进去。这种方法的核心是通过暴力枚举的方式来找出两个数组中的共同元素。
使用 filter 和 includes 方法
- 利用 filter 方法遍历第一个数组，对于数组中的每个元素，使用 includes 方法检查它是否存在于第二个数组中。filter 方法会根据 includes 方法的返回值（true 或 false）来决定是否保留该元素，最终返回一个只包含符合条件元素的新数组。
使用 reduce 方法
- reduce 方法会对数组中的每个元素执行一个回调函数，并将结果累加到一个初始值上。在这个场景中，初始值是一个空数组，回调函数会检查当前元素是否同时存在于第二个数组和结果数组中，如果满足条件就将其添加到结果数组。

2. 代码复杂度

使用 Set 的方法：代码简洁，逻辑清晰，只需要几行代码就能实现。通过 Set 的特性，避免了复杂的嵌套循环和重复检查，易于理解和维护。
双重循环方法：代码结构相对简单，但是嵌套的循环会使代码的可读性和可维护性降低，尤其是当数组长度较长时，代码的性能会显著下降。
使用 filter 和 includes 方法：代码简洁，利用了 JavaScript 数组的内置方法，一行代码就能实现功能，提高了代码的可读性。
使用 reduce 方法：代码相对复杂一些，需要理解 reduce 方法的工作原理和回调函数的使用。不过，它展示了 reduce 方法在处理数组时的灵活性。