LeetCode 1442. 形成两个异或相等数组的三元组数目

Categories:

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

题目描述

✅ 1442. 形成两个异或相等数组的三元组数目

思路分析

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

核心思路：

设前缀异或 pre[i] 表示 arr[0..i-1] 的异或。

若 pre[i] == pre[k+1]，则区间 (i, k] 异或为 0，贡献 k - i 个 j。

用哈希表维护每个前缀值出现次数与下标和，加速计算贡献。

复杂度分析：

时间复杂度：O(n)。

空间复杂度：O(n)。

import java.util.HashMap;
import java.util.Map;

class Solution {
    public int countTriplets(int[] arr) {
        Map<Integer, Integer> cnt = new HashMap<>();
        Map<Integer, Integer> sum = new HashMap<>();
        cnt.put(0, 1);
        sum.put(0, 0);

        int pre = 0;
        int ans = 0;
        for (int i = 0; i < arr.length; i++) {
            pre ^= arr[i];
            int c = cnt.getOrDefault(pre, 0);
            int s = sum.getOrDefault(pre, 0);
            ans += c * i - s;

            cnt.put(pre, c + 1);
            sum.put(pre, s + i + 1);
        }
        return ans;
    }
}

func countTriplets(arr []int) int {
    cnt := make(map[int]int)
    sum := make(map[int]int)
    cnt[0] = 1
    sum[0] = 0

    pre := 0
    ans := 0
    for i, v := range arr {
        pre ^= v
        c := cnt[pre]
        s := sum[pre]
        ans += c*i - s

        cnt[pre] = c + 1
        sum[pre] = s + i + 1
    }
    return ans
}

相似题目

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

本文作者: HGNULB

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