如何在JavaScript中找到两个数组的精确交集（保留重复项）

我有两个数字数组arr1和arr2，希望找到它们的交集，且结果中的每个元素出现的次数需与该元素在两个数组中出现次数的最小值一致。折腾了两小时写出了下面的解决方案，但它无法覆盖所有测试用例：

我的代码 #

/**
 * @param {number[]} nums1
 * @param {number[]} nums2
 * @return {number[]}
 */
var intersect = function (nums1, nums2) {
    if (nums1.length == nums2.length) {
        if (nums1.includes(nums2) && nums2.includes(nums1)) {
            return nums1[0];
        }
        if (nums1.includes(nums2)) {
            return nums2.filter((v) => nums1.includes(v));
        } else {
            return nums1.filter((v) => nums2.includes(v));
        }
    }
    if (nums1.length < nums2.length)
        return nums1.filter((v) => nums2.includes(v));
    if (nums2.length < nums1.length)
        return nums2.filter((v) => nums1.includes(v));
};

console.log(intersect([1, 2, 2, 1], [2, 2]));
console.log(intersect([1, 2, 2, 1], [2]));
console.log(intersect([9, 4, 9, 8, 4], [4, 9, 5]));
console.log(intersect([2, 1], [1, 1])); // 测试失败，预期输出 [1]

测试用例情况 #

通过的测试用例 #

• 测试用例1
  • 输入：nums1 = [1,2,2,1]，nums2 = [2,2]
  • 输出：[2,2]
• 测试用例2
  • 输入：nums1 = [4,9,5]，nums2 = [9,4,9,8,4]
  • 输出：[4,9] 或 [9,4]

未通过的测试用例 #

• 测试用例3
  • 输入：nums1 = [3,1,2]，nums2 = [1,1]
  • 预期输出：[1]

问题分析 #

你的代码核心问题在于用includes方法仅判断元素是否存在，无法跟踪元素的出现次数。比如测试用例3中，nums1里1只出现1次，nums2里出现2次，按规则应保留1个1，但你的代码会返回[1,1]，不符合要求。另外，开头的nums1.includes(nums2)逻辑完全错误——includes是检查单个元素是否在数组中，不能用来判断数组是否为另一个数组的子数组，这部分逻辑完全无效。

正确解决方案 #

方法一：哈希表统计次数 #

通过统计较短数组的元素出现次数，遍历另一个数组时按需生成结果，空间效率更高：

var intersect = function(nums1, nums2) {
    const countMap = new Map();
    const result = [];
    
    // 统计nums1中每个元素的出现次数
    for (const num of nums1) {
        countMap.set(num, (countMap.get(num) || 0) + 1);
    }
    
    // 遍历nums2，每遇到一个有效元素就加入结果并减少计数
    for (const num of nums2) {
        if (countMap.get(num) > 0) {
            result.push(num);
            countMap.set(num, countMap.get(num) - 1);
        }
    }
    
    return result;
};

方法二：排序后双指针 #

如果允许排序数组，双指针法的空间复杂度更低：

var intersect = function(nums1, nums2) {
    // 先对两个数组排序
    nums1.sort((a, b) => a - b);
    nums2.sort((a, b) => a - b);
    
    let i = 0, j = 0;
    const result = [];
    
    while (i < nums1.length && j < nums2.length) {
        if (nums1[i] === nums2[j]) {
            // 元素相等，加入结果并同步移动指针
            result.push(nums1[i]);
            i++;
            j++;
        } else if (nums1[i] < nums2[j]) {
            // nums1当前元素更小，移动i指针
            i++;
        } else {
            // nums2当前元素更小，移动j指针
            j++;
        }
    }
    
    return result;
};

这两种方法都能正确处理所有测试用例，比如测试用例3中，哈希表方法会统计nums1里1的次数为1，遍历nums2时仅第一个1会被加入结果，最终返回[1]，符合预期。

内容的提问来源于stack exchange，提问作者Ala Eddine Menai