判断相似数组的递归函数处理大输入超时，如何优化？

原代码超时核心原因 #

1. 时间复杂度达到O(n²)：每次找到第一个不相等的位置后，会遍历后续所有位置执行交换、数组复制、元素删除操作，单次循环的开销就达到O(n)，叠加后总复杂度极高，大输入下必然超时。
2. 冗余操作过多：每次递归都要复制完整的两个vector、执行erase操作，这些O(n)开销的操作完全可以避免。
3. 隐藏bug：全局变量recursionGuard存在状态残留问题，多次调用函数会得到错误结果。

优化思路 #

根据相似数组的定义，可推导得到O(n)时间复杂度的判断逻辑，无需递归：

• 两个数组长度不同直接返回false
• 遍历数组收集所有a[i] != b[i]的位置，存入差异索引列表
  • 如果差异数为0：无需交换，直接返回true
  • 如果差异数不等于2：最多交换一次最多只能修正2个位置的不一致，直接返回false
  • 如果差异数为2：取两个差异位置i、j，判断是否满足a[i] == b[j] && a[j] == b[i]，满足则返回true，否则返回false

优化后代码 #

bool solution(vector<int> a, vector<int> b) {
    if (a.size() != b.size()) return false;
    vector<int> diff;
    for (int i = 0; i < a.size(); i++) {
        if (a[i] != b[i]) {
            diff.push_back(i);
            // 提前终止：差异超过2个直接返回，无需完成遍历
            if (diff.size() > 2) return false;
        }
    }
    if (diff.empty()) return true;
    if (diff.size() != 2) return false;
    int i = diff[0], j = diff[1];
    return a[i] == b[j] && a[j] == b[i];
}

内容的提问来源于stack exchange，提问作者Joel D'Souza