求两个有序数组交集对应首数组的索引数组：我的解法为何错误？

核心问题：只实现了单一匹配逻辑，未覆盖重复元素的多可能性 #

从题目给出的输出示例（比如输入1有3种有效结果、输入2有2种）可以看出，题目要求返回所有符合条件的arr1索引数组，而你的代码只能生成其中一种贪心匹配的结果，这就是面试官判定错误的关键。

具体逻辑缺陷 #

你的双指针同步前进逻辑：一旦匹配到相等元素，就同时移动i和j，这种方式只会选择最靠前的元素进行匹配，但当数组存在重复元素时，同一个值的不同索引组合都是有效的交集对应。比如输入示例1中：

• arr1的[2,2,2]和arr2的[2,2]可以有3种匹配组合，你的代码只返回了[0,1,2]这一种，漏掉了另外两种有效结果。

修正方案：用回溯法生成所有可能结果 #

下面是能覆盖所有情况的实现，通过回溯尝试所有合法的匹配路径：

function intersectionIndexes(compareItemsFn, length1, length2) {
    const results = [];
    
    function backtrack(i, j, current) {
        // 当arr2遍历完成时，记录当前有效结果
        if (j === length2) {
            results.push([...current]);
            return;
        }
        // arr1遍历完直接终止
        if (i === length1) {
            return;
        }
        
        const cmp = compareItemsFn(i, j);
        if (cmp === 0) {
            // 选择当前i加入结果，继续匹配下一组元素
            current.push(i);
            backtrack(i + 1, j + 1, current);
            current.pop();
            
            // 跳过当前i，尝试用arr1后续相同元素匹配当前j（避免重复结果）
            let nextI = i + 1;
            while (nextI < length1 && compareItemsFn(i, nextI) === 0) {
                nextI++;
            }
            backtrack(nextI, j, current);
        } else if (cmp === -1) {
            // arr1当前元素更小，跳过所有相同元素后继续
            let nextI = i + 1;
            while (nextI < length1 && compareItemsFn(i, nextI) === 0) {
                nextI++;
            }
            backtrack(nextI, j, current);
        } else {
            // arr2当前元素更小，跳过所有相同元素后继续
            let nextJ = j + 1;
            while (nextJ < length2 && compareItemsFn(nextJ, j) === 0) {
                nextJ++;
            }
            backtrack(i, nextJ, current);
        }
    }
    
    backtrack(0, 0, []);
    return results;
}

测试验证 #

• 输入示例1运行后会返回[[0,1,2], [0,1,3], [0,2,3]]，完全匹配题目给出的输出。
• 输入示例2运行后会返回[[0,1,3,5,8,9], [0,2,3,5,8,9]]，符合题目要求。

内容的提问来源于stack exchange，提问作者Vasilii Zalizniak