Leetcode 1310

今天又是爆肝的一天 , 感觉这个月应该是异或月了，全是异或题（痛哭）

今天的每日一题是1310. 子数组异或查询

queries数组提供的是查询的范围

然后返回一个包含所有查询结果的数组

我们可以用类似 prefix sum 前缀和

采取 prefix XOR前缀异或 来完成该题

对于每个查询都要计算，因此我们应该优化每个查询的计算时间

queries(L , R)

= array[L] ⊕ …. ⊕ array[R] , 又 x ⊕ x = 0

= ( array[0] ⊕ …. ⊕ array[L - 1] ) ⊕ ( array[0] ⊕ …. ⊕ array[L - 1] ) ⊕ ( array[L] ⊕ …. ⊕ array[R] )

= ( array[0] ⊕ …. ⊕ array[L - 1] ) ⊕ ( array[0] ⊕ …. ⊕ array[R] )

= XORS[L] ⊕ XORS[R + 1]

XORS为存储 前缀异或 的数组 , 当L = 0时，XORS[0] = 0 ，以上等式仍然成立

数组不变，求区间 , 都可以用prefix来解决

public static int[] xorQueries(int[] arr, int[][] queries) {
    int n = arr.length;
    int[] pre = new int[n + 1];
    //计算每个位置的前缀和 pre[i] 表示前i项的异或和
    for (int i = 1; i <= n; i++) {
        pre[i] = pre[i - 1] ^ arr[i - 1];
    }
    int[] ans = new int[queries.length];
    int i = 0;

    /**
     * for (int i = 0; i < m; i++) {
     *    ans[i] = xors[queries[i][0]] ^ xors[queries[i][1] + 1];
     * }
     */

    for (int[] query : queries) {
        //前面多异或的部分，再重复异或一次就可以抵消了
        //假设 求 [1, 2]，那么对于 [0, 2] 来说就是多异或了 [0, 0] 这个结果
        //根据 两个相同值异或结果为 0，那么我们可以再异或一次 [0, 0] 就将 [0, 0] 给抵消掉了
        //pre[query[0]]代表了[0, 0]异或 pre[query[1] + 1]代表了[0, 2]异或 其中[0, 0]异或两次
        //最后相当于[1, 2]异或
        ans[i++] = pre[query[0]] ^ pre[query[1] + 1];
    }
    return ans;
}

时间复杂度：O(n+m) , n , m 分别为array , queries数组的长度

空间复杂度：O(n)

类似题目有307. 区域和检索 - 数组可修改