C++递归实现两数组交集：如何避免重复添加相同值？

嘿，我明白你现在的问题了——用递归找两个数组的交集，结果本该只出现一次的元素被重复添加了对吧？这大概率是你的递归逻辑没控制好遍历的节奏，导致同一个交集元素被不同的递归路径多次匹配到。我来帮你拆解问题，给出可行的解决方案：

问题根源 #

举个你提到的例子：数组{1,2,3,4}和{5,6,2,...}，你的递归可能会通过不同的路径多次定位到arr1[1]（也就是2）和arr2[2]（也就是2）这个匹配对，比如从(i=0,j=0)一步步递归到(i=1,j=2)，又从(i=1,j=0)递归到(i=1,j=2)，每次匹配到都往vector里加一次，结果就出现了重复。

这种情况通常是因为你的递归没有在找到匹配后及时推进两个数组的索引，或者同时开启了多个会重复访问同一元素对的递归分支。

两种可行的递归解决方案 #

方案1：先排序再用双指针递归（推荐） #

先把两个数组排序，然后用双指针式的递归逻辑，确保每个元素只被比较一次，完全避免重复匹配：

#include <vector>
#include <algorithm>

// 递归函数：i是arr1的当前遍历索引，j是arr2的当前遍历索引，result存储交集结果
void findIntersectionRecursive(const std::vector<int>& arr1, const std::vector<int>& arr2, int i, int j, std::vector<int>& result) {
    // 终止条件：任一数组遍历完成就停止递归
    if (i >= arr1.size() || j >= arr2.size()) {
        return;
    }

    if (arr1[i] == arr2[j]) {
        // 找到共同元素，加入结果集合
        result.push_back(arr1[i]);
        // 同时推进两个数组的索引，避免再次匹配当前元素
        findIntersectionRecursive(arr1, arr2, i + 1, j + 1, result);
    } else if (arr1[i] < arr2[j]) {
        // arr1当前元素更小，推进arr1的索引寻找更大的元素
        findIntersectionRecursive(arr1, arr2, i + 1, j, result);
    } else {
        // arr2当前元素更小，推进arr2的索引寻找更大的元素
        findIntersectionRecursive(arr1, arr2, i, j + 1, result);
    }
}

// 调用示例
int main() {
    std::vector<int> arr1 = {1, 2, 3, 4};
    std::vector<int> arr2 = {5, 6, 2, 7};
    std::vector<int> result;

    // 先对两个数组排序，为双指针递归做准备
    std::sort(arr1.begin(), arr1.end());
    std::sort(arr2.begin(), arr2.end());

    // 从两个数组的起始位置开始递归
    findIntersectionRecursive(arr1, arr2, 0, 0, result);

    // 此时result中只会有一个2，没有重复
    return 0;
}

这个方案的优势是逻辑清晰，时间复杂度主要由排序决定（O(n log n)），递归过程没有冗余的重复比较，非常适合你的场景。

方案2：无排序递归（适配元素唯一的场景） #

如果不想排序，可以在找到匹配后同时推进两个数组的索引，避免重复匹配同一元素对：

#include <vector>
#include <algorithm>

void findIntersectionNoSort(const std::vector<int>& arr1, const std::vector<int>& arr2, int i, int j, std::vector<int>& result) {
    if (i >= arr1.size() || j >= arr2.size()) {
        return;
    }

    if (arr1[i] == arr2[j]) {
        // 先检查结果中是否已有该元素（避免数组本身有重复元素时的重复添加）
        if (std::find(result.begin(), result.end(), arr1[i]) == result.end()) {
            result.push_back(arr1[i]);
        }
        // 推进两个索引，跳过当前匹配的元素
        findIntersectionNoSort(arr1, arr2, i + 1, j + 1, result);
    } else {
        // 分别递归跳过arr1当前元素，或跳过arr2当前元素
        findIntersectionNoSort(arr1, arr2, i + 1, j, result);
        findIntersectionNoSort(arr1, arr2, i, j + 1, result);
    }
}

// 调用示例
int main() {
    std::vector<int> arr1 = {1, 2, 3, 4};
    std::vector<int> arr2 = {5, 6, 2, 7};
    std::vector<int> result;

    findIntersectionNoSort(arr1, arr2, 0, 0, result);

    // 结果中只会有一个2
    return 0;
}

这个方案不需要排序，但递归路径会更多，效率稍低。另外如果数组本身包含重复元素，需要在添加前检查元素是否已存在于结果中，避免重复。

核心思路 #

递归的关键是明确递归状态的推进逻辑，确保每个元素对只被处理一次，或者在找到匹配后及时跳过当前元素，切断重复匹配的路径。排序后的双指针递归是最稳妥高效的方式，非常适合你刚学习递归时用来理解逻辑。

内容的提问来源于stack exchange，提问作者Ryan Jin