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

约 5 分钟
文章信息 6 个分类 5 个标签
分类
LeetCode CodeTop 中等 未解决 1-2 阿里
标签
数组 哈希表 数学 位运算 前缀和

题目描述

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

image-20260929082551651

image-20260929082551748

题意分析

统计满足 0 <= i < j <= k < n 的三元组，使相邻两段 arr[i..j-1] 与 arr[j..k] 的异或值相等。两段都必须非空，j 是第二段的起点。

要统计的是下标三元组，不只是某个零异或区间的数量。同一对区间端点可能允许多个不同的分割点，每个分割点都对应一个独立答案。

解法：前缀异或 + 计数

核心思路

[!blue]

两个异或值相等，等价于把它们再异或得到零。因此只要整个连续区间 arr[i..k] 的异或为零，就可以在内部任意位置切成两段，它们的异或都会相等。这样先把分割点 j 从匹配条件中消去。

定义前缀位置 q 的异或为前 q 个元素的异或，位置零表示空前缀，其值为零。区间 arr[i..k] 的异或等于前缀位置 i 与 k + 1 的异或，所以它为零恰好意味着两个前缀值相同。

设这两个前缀位置为 p = i、q = k + 1。为了让两段都非空，分割点 j 只能从 p + 1 选到 q - 1，一共 q - p - 1 种。相等前缀配对贡献的不是固定的一，而是这两个位置之间可选的切点数。

扫描当前前缀位置 q 时，如果同值历史前缀有 count 个，它们的位置总和为 positionSum，把每个位置的贡献相加，就得到 count * (q - 1) - positionSum。因此每种前缀异或值只需保存出现次数和位置和，不必逐个枚举历史起点。

初始登记值为零、位置为零的空前缀，才能覆盖从数组开头开始的区间。每轮先查询历史贡献，再增加当前位置的次数与位置和，保证配对对象都严格早于当前前缀。

每个 q 对应唯一的右端 k，每个历史 p 对应唯一的左端 i，距离公式又恰好计入全部内部 j，所以所有合法三元组被计数一次，不会重复或遗漏。

解题步骤

  1. 初始化当前前缀异或为零，预登记 counts[0] = 1、positionSums[0] = 0。
  2. 将前缀位置 q 从一递增，每轮异或进 arr[q - 1]。
  3. 查询当前异或值的历史出现次数与位置和，累加 count * (q - 1) - positionSum。
  4. 再登记当前位置：次数加一，位置和加 q。
  5. 完成全部前缀后返回总贡献。

代码实现

class Solution {
    public int countTriplets(int[] arr) {
        Map<Integer, Integer> counts = new HashMap<>();
        Map<Integer, Integer> positionSums = new HashMap<>();

        // 空前缀位置零出现一次，覆盖从数组开头开始的区间。
        counts.put(0, 1);
        positionSums.put(0, 0);

        int prefix = 0;
        int answer = 0;

        for (int q = 1; q <= arr.length; q++) {
            prefix ^= arr[q - 1];
            int count = counts.getOrDefault(prefix, 0);
            int positionSum = positionSums.getOrDefault(prefix, 0);

            // 同值历史前缀批量贡献距离减一，位置和用于消去各起点。
            answer += count * (q - 1) - positionSum;

            // 先查询再登记当前位置，避免自身配对产生错误贡献。
            counts.put(prefix, count + 1);
            positionSums.put(prefix, positionSum + q);
        }

        return answer;
    }
}

func countTriplets(arr []int) int {
    // 空前缀位置零出现一次，覆盖从数组开头开始的区间。
    counts := map[int]int{0: 1}
    positionSums := map[int]int{0: 0}

    prefix := 0
    answer := 0
    for q := 1; q <= len(arr); q++ {
        prefix ^= arr[q-1]
        count := counts[prefix]
        positionSum := positionSums[prefix]
        // 同值历史前缀批量贡献距离减一，位置和用于消去各起点。
        answer += count*(q-1) - positionSum

        // 先查询再登记当前位置，避免自身配对产生错误贡献。
        counts[prefix] = count + 1
        positionSums[prefix] = positionSum + q
    }
    return answer
}

复杂度分析

设数组长度为 $n$。

  • 时间复杂度：期望 $O(n)$，每个前缀只做常数次哈希查询和更新。
  • 辅助空间复杂度：$O(n)$，两张表最多记录 $n+1$ 个不同的前缀状态。

关键点总结

[!green]

  • 两段异或相等等价于合并区间异或为零，再等价于两端前缀相同。
  • 一个端点对贡献距离减一，因为两段都必须非空。
  • 历史次数与位置和将全部距离贡献合并成一个公式。
  • 前缀位置与数组下标相差一，查询在登记当前状态之前。

易错点总结

[!yellow]

  • 漏记空前缀，会漏掉左端为数组起点的合法区间。
  • 每对相同前缀只加一，会少算内部多个分割点；使用 q - p 又会多算使某段为空的位置。
  • 位置和应登记 q，不是刚读取的数组下标 q - 1。
  • 先登记当前位置再查询，会让前缀与自身配对，产生负一的错误贡献。
  • 只保存出现次数不保存位置和，无法批量计算不同历史起点对应的不同距离。

相似题目

题目 难度 关联与区别
1310. 子数组异或查询 中等 相等的两段异或等价于合并区间异或为0，可转成两个相同前缀异或值。
560. 和为 K 的子数组 中等 同样按相同前缀分组计数，本题还要把区间内部可选切点数量计入贡献。
转载与许可
作者
链接 https://hgnulb.github.io/blog/2023/44285342
许可 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！