如何找到异或结果具偶校验的最长子数组？能否优化O(n²)解法？

问题拆解 #

你的代码核心逻辑是遍历所有子数组，计算子数组的异或结果，判断其二进制中1的个数是否为偶数，最终记录最长符合条件的子数组长度。原方案时间复杂度为O(n² log n)（其中bin函数每次调用需O(log n)时间统计1的个数），完全可以优化到**O(n)**级别。

关键优化思路 #

注意到一个核心等价关系：

异或结果的二进制1的个数为偶数，等价于子数组中所有元素的二进制1的个数的奇偶性之和为偶数。

因为异或运算中，相同位的1会相互抵消，最终结果的1的个数奇偶性，等于所有参与异或元素的1的个数的奇偶性的累加和的奇偶性（加法模2等价于异或）。基于此，我们可以把问题转化为经典的「最长和为偶数的子数组」问题，用前缀哈希表实现线性时间求解。

具体优化步骤 #

1. 预处理奇偶性：对每个元素，计算其二进制1的个数的奇偶性（用0表示偶数个1，1表示奇数个1），可以用C++内置的__builtin_popcount函数替代手写的bin函数，时间复杂度从O(log n)降到O(1)。
2. 前缀奇偶和：维护一个前缀奇偶和变量，每遍历一个元素就更新该值（用异或替代加法模2，效率更高）。
3. 哈希表记录首次出现位置：用哈希表存储每种前缀奇偶和第一次出现的索引。当再次遇到相同的前缀奇偶和时，两个索引之间的子数组就是符合条件的，计算长度并更新最大值。

优化后代码示例 #

#include <iostream>
#include <unordered_map>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    vector<int> a = {/* 你的输入数组 */};
    int n = a.size();
    int max_len = 0;
    int prefix_parity = 0;
    unordered_map<int, int> first_occur;
    first_occur[0] = -1; // 前缀和为0的初始索引，对应子数组从0到当前位置

    for (int i = 0; i < n; ++i) {
        // 计算当前元素的1的个数的奇偶性
        int bit_count = __builtin_popcount(a[i]);
        int curr_parity = bit_count % 2;
        prefix_parity ^= curr_parity; // 更新前缀奇偶和

        if (first_occur.count(prefix_parity)) {
            // 计算符合条件的子数组长度
            max_len = max(max_len, i - first_occur[prefix_parity]);
        } else {
            // 记录该奇偶性首次出现的索引
            first_occur[prefix_parity] = i;
        }
    }

    cout << "最长符合条件的子数组长度：" << max_len << endl;
    return 0;
}

复杂度分析 #

• 时间复杂度：O(n)，仅需遍历数组一次，每个元素的处理都是O(1)操作。
• 空间复杂度：O(1)，因为前缀奇偶和只有0、1两种可能，哈希表最多存储2个键值对，属于常数级空间。

原代码的小优化（不改变O(n²)复杂度） #

如果暂时不想重构逻辑，也可以先替换bin函数为__builtin_popcount，将原代码的时间复杂度从O(n² log n)降到O(n²)：

// 替换原bin函数
int bin(int n) {
    return __builtin_popcount(n);
}

内容的提问来源于stack exchange，提问作者Anvita Mahajan