Medium

题目描述

给你一个由正整数组成的数组 arr，请你计算所有可能查询的结果并返回。

查询的格式为：queries[i] = [lefti, righti]

对于每个查询 i，请你计算从 lefti 到 righti 的元素异或结果，即：arr[lefti] XOR arr[lefti + 1] XOR ... XOR arr[righti]。

请返回一个数组 answer，其中 answer[i] 是第 i 个查询的结果。

示例 1：

输入：arr = [1,3,4,8], queries = [[0,1],[1,2],[0,3],[3,3]]
输出：[2,7,14,8]
解释：
数组中元素的二进制表示形式为：
1 = 0001 
3 = 0011 
4 = 0100 
8 = 1000 
查询的 XOR 值为：
[0,1] = 1 xor 3 = 2 
[1,2] = 3 xor 4 = 7 
[0,3] = 1 xor 3 xor 4 xor 8 = 14 
[3,3] = 8

示例 2：

输入：arr = [4,8,2,10], queries = [[2,3],[1,3],[0,0],[0,3]]
输出：[8,0,4,4]

提示：

  • 1 <= arr.length, queries.length <= 3 * 10^4
  • 1 <= arr[i] <= 10^9
  • queries[i].length == 2
  • 0 <= lefti <= righti < arr.length

解题思路

这道题要求计算子数组的异或值，如果每次查询都重新计算会导致时间复杂度过高。我们可以利用前缀异或来优化。

核心思想： 异或运算有一个重要性质：x ^ x = 0，x ^ 0 = x。这意味着如果我们知道了从索引 0 到某个位置的异或值，就可以快速计算任意子数组的异或值。

具体做法：

  1. 构建前缀异或数组 prefix，其中 prefix[i] 表示从索引 0 到索引 i-1 的所有元素的异或值
  2. 对于查询 [left, right]，子数组的异或值等于 prefix[right+1] ^ prefix[left]

为什么这样做是正确的？

  • prefix[right+1] = arr[0] ^ arr[1] ^ ... ^ arr[right]
  • prefix[left] = arr[0] ^ arr[1] ^ ... ^ arr[left-1]
  • prefix[right+1] ^ prefix[left] = (arr[0] ^ ... ^ arr[left-1] ^ arr[left] ^ ... ^ arr[right]) ^ (arr[0] ^ ... ^ arr[left-1])
  • 由于 x ^ x = 0，前面相同的部分会被消除，剩下的就是 arr[left] ^ ... ^ arr[right]

这种方法将每次查询的时间复杂度从 O(n) 降低到 O(1)。

代码实现

class Solution {
public:
    vector<int> xorQueries(vector<int>& arr, vector<vector<int>>& queries) {
        int n = arr.size();
        vector<int> prefix(n + 1, 0);
        
        // 构建前缀异或数组
        for (int i = 0; i < n; i++) {
            prefix[i + 1] = prefix[i] ^ arr[i];
        }
        
        vector<int> result;
        for (auto& query : queries) {
            int left = query[0], right = query[1];
            result.push_back(prefix[right + 1] ^ prefix[left]);
        }
        
        return result;
    }
};

class Solution:
    def xorQueries(self, arr: List[int], queries: List[List[int]]) -> List[int]:
        n = len(arr)
        prefix = [0] * (n + 1)
        
        # 构建前缀异或数组
        for i in range(n):
            prefix[i + 1] = prefix[i] ^ arr[i]
        
        result = []
        for left, right in queries:
            result.append(prefix[right + 1] ^ prefix[left])
        
        return result

public class Solution {
    public int[] XorQueries(int[] arr, int[][] queries) {
        int n = arr.Length;
        int[] prefix = new int[n + 1];
        
        // 构建前缀异或数组
        for (int i = 0; i < n; i++) {
            prefix[i + 1] = prefix[i] ^ arr[i];
        }
        
        int[] result = new int[queries.Length];
        for (int i = 0; i < queries.Length; i++) {
            int left = queries[i][0];
            int right = queries[i][1];
            result[i] = prefix[right + 1] ^ prefix[left];
        }
        
        return result;
    }
}

/**
 * @param {number[]} arr
 * @param {number[][]} queries
 * @return {number[]}
 */
var xorQueries = function(arr, queries) {
    const n = arr.length;
    const prefix = new Array(n + 1).fill(0);
    
    // 构建前缀异或数组
    for (let i = 0; i < n; i++) {
        prefix[i + 1] = prefix[i] ^ arr[i];
    }
    
    const result = [];
    for (const [left, right] of queries) {
        result.push(prefix[right + 1] ^ prefix[left]);
    }
    
    return result;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度说明
时间复杂度O(n + m)n 为数组长度，m 为查询数量。构建前缀数组需要 O(n)，处理查询需要 O(m)
空间复杂度O(n)需要额外的前缀数组存储空间