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

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

题目描述

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

题意分析

要数出满足 0 <= i < j <= k < n 的三元组 (i, j, k) 的个数，条件是 a == b，其中 a 是 arr[i] ^ ... ^ arr[j-1]，b 是 arr[j] ^ ... ^ arr[k]。注意 j 的下界是 i + 1，所以 a 段至少含一个元素；k 的下界是 j，所以 b 段也至少含一个元素。两段紧挨着，中间不留空隙。

第一层改写必须马上做出来：异或的自反性告诉我们 a == b 等价于 a ^ b == 0，而 a ^ b 恰好就是 arr[i] ^ ... ^ arr[k] 这一整段的异或。也就是说，j 根本不影响条件是否成立——只要区间 [i, k] 的整体异或为 0，j 在 [i+1, k] 里随便取都合法。

这个改写把「三重枚举」降成「二重枚举 + 计数」：先找出所有异或为 0 的区间 [i, k]，每个这样的区间贡献 k - i 个三元组（j 有 k - i 种取法）。

约束方面，数组长度只有 300 量级，$O(n^2)$ 甚至 $O(n^3)$ 都能过，但面试期待的是能一路推到 $O(n)$。数值上界 $10^8$，异或结果仍在 int 范围内，不必担心溢出；答案上界约 $n^3/6$，int 也装得下。

边界要注意「空前缀」：区间 [0, k] 的异或需要用到「前 0 个元素的异或」这个虚拟状态，它的值是 0，必须被当作一个合法的历史状态参与匹配，否则所有以下标 0 开头的区间都会被漏掉。

解法：前缀异或 + 计数

核心思路

定义前缀异或 prefix[t] 为前 t 个元素的异或，prefix[0] = 0。原条件可写成

\[a = prefix[j] \oplus prefix[i], \qquad b = prefix[k+1] \oplus prefix[j]\]

因为相同数异或为 0，a == b 等价于 prefix[i] == prefix[k+1]。中间位置 j 从判定条件里消失了：固定一个整体异或为 0 的区间 [i,k] 后，j 可以取 i+1..k，一共 k-i 种。

改用前缀位置 p=i、q=k+1，每对相等前缀 prefix[p] == prefix[q] 的贡献就是 q-p-1。扫描当前前缀位置 q 时，若相同异或值的历史位置集合为 S，总贡献为

\[\sum_{p \in S}(q-p-1) = \lvert S\rvert (q-1) - \sum_{p \in S}p\]

因此对每个前缀异或值同时维护出现次数 count 和出现位置之和 positionSum。

循环不变量是：处理位置 q 之前，两张表恰好统计 prefix[0..q-1]。先按公式查询贡献，再把当前位置 q 写入表，便只会与严格更早的前缀配对。每个合法三元组唯一对应一对相等前缀和其中一个 j，所以计数不重不漏。

解题步骤

  • 初始化空前缀：异或值 0 在前缀位置 0 出现一次，位置和为 0。
  • 对 q = 1..n，先执行 prefix ^= arr[q-1] 得到 prefix[q]。
  • 读取相同前缀值的历史次数 count 与位置和 positionSum。
  • 累加 count * (q - 1) - positionSum。
  • 查询完成后再记录当前位置：次数加 1，位置和加 q。

对 arr = [2,3,1,6,7]，前缀异或为 [0,2,1,0,6,1]。相等位置对 (0,3) 贡献 2，(2,5) 贡献 2，总答案为 4。

边界反例 arr=[1,1]：prefix[0]=prefix[2]=0，位置对 (0,2) 贡献 2-0-1=1。若漏掉空前缀，答案会错误变成 0。

代码实现

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

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
}

复杂度分析

  • 时间复杂度：平均 $O(n)$，每个前缀位置执行常数次哈希表操作。
  • 空间复杂度：$O(n)$，两张表最多记录 $n+1$ 个不同的前缀异或值。

关键点总结

  • 两段异或相等可合并为整个区间异或为 0，等价于两端前缀异或相等。
  • 对相等前缀位置 p < q，中间分割点有 q-p-1 个；贡献是距离，不是简单加 1。
  • 批量求距离和需要同时保存历史位置的数量与位置总和。
  • 表中存的是前缀位置；扫描数组下标 q-1 后，写入的位置是 q。
  • 空前缀位置 0 必须预置，且必须先查询历史、后插入当前前缀。

易错点总结

  • 漏掉空前缀：[1,1] 的合法区间从下标 0 开始，会被完全漏算。
  • 每对相等前缀只加 1：[2,3,1] 的区间 [0,2] 有两个合法 j，应贡献 2。
  • 贡献写成 q-p：会允许 j=i 形成空左段；正确数量是 q-p-1。
  • 把数组下标 q-1 加入位置和：表记录的是前缀位置，整体少 1 会使后续距离系统性偏大。
  • 先插入当前前缀再查询：当前位置会与自身配对，并按公式贡献 -1，导致每轮错误少算。
  • 只保存出现次数：无法计算所有 q-p-1 的加权和，只能退回枚举历史位置的 $O(n^2)$ 做法。

相似题目

题目 难度 考察点
560. 和为 K 的子数组 中等 把异或换成加法，只需计数不需下标和，是本题去掉加权后的原型
974. 和可被 K 整除的子数组 中等 匹配键从「前缀值相等」变成「前缀值同余」，负数取模是额外坑点
525. 连续数组 中等 0/1 映射成 ±1 后同样找相等前缀，但要的是最长长度而非数量
1310. 子数组异或查询 中等 只用到前缀异或做区间查询，没有配对计数，是本题前半段技巧的裸题
136. 只出现一次的数字 简单 考的是异或的自反与交换律本身，用全体异或抵消成对元素
1. 两数之和 简单 同样是「边扫边查历史表」的骨架，但要返回下标对而不是统计个数