一、题目

有一个正整数数组 arr，现给你一个对应的查询数组 queries，其中 queries[i] = [Li, Ri]。

对于每个查询 i，请你计算从 Li 到 Ri 的 XOR 值（即 arr[Li] xor arr[Li+1] xor … xor arr[Ri]）作为本次查询的结果。

并返回一个包含给定查询 queries 所有结果的数组。

点击查看原题

二、思路

该题首先想到的就是暴力法，直接根据题意，每次都从arr[Li]依次异或运算到arr[Ri]即可。
但是这样做的时间复杂度较高，需要使用记忆化来缩减时间复杂度，不需要重复计算异或，直接可以获得需要的值。根据异或运算中的规则，同样的数字经历偶数次运算即可抵消（如：num^num=0）。
设定一个数组memo，memo[i]=arr[0]^arr[1]^…^arr[i-1]，也就是0到i-1项的异或结果，那么需要的答案ans[i]=arr[Li]^arr[Li+1]^…^arr[Ri]=memo[Li]^memo[Ri+1]。

三、代码

  1. class Solution {
  2.     public int[] xorQueries(int[] arr, int[][] queries) {
  3.         int[] memo = new int[arr.length + 1];
  4.         memo[0] = 0;
  5.         for (int i = 1; i < memo.length; i++) {
  6.             memo[i] = memo[i-1]^arr[i-1];
  7.         }
  8.         int[] ans = new int[queries.length];
  9.         for (int i = 0; i < queries.length; i++) {
  10.             ans[i] = memo[queries[i][0]]^memo[queries[i][1] + 1];
  11.         }
  12.         return ans;
  13.     }
  14. }

空间复杂度为O(arr.length)，时间复杂度为O(queries.length + arr.length)。