LeetCode 1310. 子数组异或查询

Categories:

题目描述
思路分析
1. 解法一：前缀异或（推荐）
相似题目

题目描述

✅ 1310. 子数组异或查询

思路分析

解法一：前缀异或（推荐）

核心思路：

预处理前缀异或 pre[i] = arr[0] ^ ... ^ arr[i-1]。

查询 [l, r] 的异或为 pre[r+1] ^ pre[l]。

复杂度分析：

时间复杂度：O(n + q)，其中 q 为查询数量。

空间复杂度：O(n)。

class Solution {
    public int[] xorQueries(int[] arr, int[][] queries) {
        int n = arr.length;
        int[] pre = new int[n + 1];
        for (int i = 0; i < n; i++) {
            pre[i + 1] = pre[i] ^ arr[i];
        }

        int[] res = new int[queries.length];
        for (int i = 0; i < queries.length; i++) {
            int l = queries[i][0];
            int r = queries[i][1];
            res[i] = pre[r + 1] ^ pre[l];
        }
        return res;
    }
}

func xorQueries(arr []int, queries [][]int) []int {
    n := len(arr)
    pre := make([]int, n+1)
    for i := 0; i < n; i++ {
        pre[i+1] = pre[i] ^ arr[i]
    }

    res := make([]int, len(queries))
    for i, q := range queries {
        l, r := q[0], q[1]
        res[i] = pre[r+1] ^ pre[l]
    }
    return res
}

相似题目

题目	难度	考察点
1734. 解码异或后的排列	中等	前缀异或
1720. 解码异或后的数组	简单	前缀异或
1486. 数组异或操作	简单	位运算
268. 丢失的数字	简单	异或
421. 数组中两个数的最大异或值	中等	位运算

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2023/81852427