形成两个异或相等数组的三元组数目 图解题解
这道题到底在问什么
- 输入
- arr = [2,3,1,6,7]
- 输出
- 4(三元组 (0,1,2)(0,2,2)(2,3,4)(2,4,4))
- 输入
- arr = [1,1,1,1,1]
- 输出
- 10
- 输入
- arr = [2,3]
- 输出
- 0
最优解：一步一步想明白
- 3记牢这条主线:a 等于 b 就是 arr[i..k] 整段异或为 0,再用前缀异或把它翻译成 pre[i] 等于 pre[k+1],也就是在 pre 里找相等的两格。下面每一帧都在套这条线。
- 4上面这排是 arr = [2, 3, 1, 6, 7]。右边面板是要建的前缀异或数组 pre,它比 arr 多一格,一共 6 格,现在全是问号。第一格 pre[0] 我们约定等于 0,它代表一段什么都不异或的空区间,异或上 0 谁都不变,这个起点待会儿很有用。
- 5异或是按二进制位算的,先把每个数写成三位二进制看清:2 是 010,3 是 011,1 是 001,6 是 110,7 是 111。两个数异或时逐位比较,这一位相同得 0、不同得 1,各位互不影响。心里有了这张表,后面建前缀、判断整段是否为 0 都顺。
- 6先把 pre[0] 写成 0,它表示前 0 个数的异或,也就是什么都不异或,结果是 0。0 是异或的零元,谁异或 0 都等于它自己。正因如此,等会儿从下标 0 开头的区间,左端落在 pre[0] 上特别好处理。
- 7把 arr[0] = 2 接进来。新的前缀值 pre[1] 等于上一格 pre[0] = 0 再异或这个 2,二进制是 000 异或 010 等于 010,也就是 2。记到 pre[1] 这一格。
- 8把 arr[1] = 3 接进来。新的前缀值 pre[2] 等于上一格 pre[1] = 2 再异或这个 3,二进制是 010 异或 011 等于 001,也就是 1。记到 pre[2] 这一格。
- 9把 arr[2] = 1 接进来。新的前缀值 pre[3] 等于上一格 pre[2] = 1 再异或这个 1,二进制是 001 异或 001 等于 000,也就是 0。记到 pre[3] 这一格。
- 10把 arr[3] = 6 接进来。新的前缀值 pre[4] 等于上一格 pre[3] = 0 再异或这个 6,二进制是 000 异或 110 等于 110,也就是 6。记到 pre[4] 这一格。
- 11把 arr[4] = 7 接进来。新的前缀值 pre[5] 等于上一格 pre[4] = 6 再异或这个 7,二进制是 110 异或 111 等于 001,也就是 1。记到 pre[5] 这一格。
- 12前缀异或数组建好了,从左到右是 0、2、1、0、6、1。从这一帧起,舞台上摆的就是这排 pre,原来的 arr 退到幕后。记住每格含义:pre[t] 是 arr 前 t 个数的异或,比如 pre[3] = 0 就是 arr[0] 异或 arr[1] 异或 arr[2]。
- 13先看一个具体例子体会转化。arr[0..2] 的整段异或等于 pre[3] 异或 pre[0],也就是 0 异或 0 等于 0。为什么能这么算?因为 pre[3] 含 arr 前三个、pre[0] 含前零个,两者异或时公共前缀成对抵消,只剩 arr[0..2]。这里 pre[0] 和 pre[3] 正好相等,异或就是 0,说明 arr[0..2] 整段异或为 0,这正是我们要找的信号。
- 14把规律说清:在 pre 里找到相等的两格,左边位置叫 p、右边叫 q。它对应 i 等于 p、k 等于 q 减 1,这时 arr[i..k] 整段异或为 0。中间的 j 满足 i < j ≤ k,能放的位置有 k 减 i 个,也就是 q 减 p 减 1 个。所以每找到一对相等前缀,就往答案里加 q 减 p 减 1。下面就在 pre 上从左到右扫,边扫边配对。
- 15扫到第 0 格,pre[0] = 0。查一下前面的记录,这个值之前没出现过,所以暂时配不成对,把它的位置 0 记进面板,继续往后扫。答案目前还是 0。
- 16扫到第 1 格,pre[1] = 2。查一下前面的记录,这个值之前没出现过,所以暂时配不成对,把它的位置 1 记进面板,继续往后扫。答案目前还是 0。
- 17扫到第 2 格,pre[2] = 1。查一下前面的记录,这个值之前没出现过,所以暂时配不成对,把它的位置 2 记进面板,继续往后扫。答案目前还是 0。
- 18扫到第 3 格,pre[3] = 0。面板里这个值之前在位置 0 出现过,绿色这几格就是相等前缀,正好配成对。每一对都意味着中间夹着一段整段异或为 0 的区间,下一帧来数它们各贡献几个三元组。
- 19逐对结算:(0, 3) 贡献 3 减 0 减 1 = 2。意思是 i 取 0、k 取 2,中间的 j 各有那么多种放法。把贡献加进答案,现在累计是 2。算完别忘了把当前位置 3 也记进面板,因为它以后可能再和更靠右的相等格配对。
- 20扫到第 4 格,pre[4] = 6。查一下前面的记录,这个值之前没出现过,所以暂时配不成对,把它的位置 4 记进面板,继续往后扫。答案目前还是 2。
- 21扫到第 5 格,pre[5] = 1。面板里这个值之前在位置 2 出现过,绿色这几格就是相等前缀,正好配成对。每一对都意味着中间夹着一段整段异或为 0 的区间,下一帧来数它们各贡献几个三元组。
- 22逐对结算:(2, 5) 贡献 5 减 2 减 1 = 2。意思是 i 取 2、k 取 4,中间的 j 各有那么多种放法。把贡献加进答案,现在累计是 4。通用扫描里会把当前位置也记进面板,不过本例已经到最后一格,不会再产生新配对。
- 23扫完整排 pre,一共配出两对相等前缀:(0, 3) 贡献 2 个、(2, 5) 贡献 2 个,加起来是 4。对照真实三元组就是 (0,1,2)、(0,2,2)、(2,3,4)、(2,4,4),正好和题目给的 (0,1,2)、(0,2,2)、(2,3,4)、(2,4,4) 一一对上。整道题就靠前缀异或把整段异或为 0 翻译成两格相等,一遍扫描就数完。
⚠️ 容易写错的地方
✗ 错：把 a 等于 b 拆成两段分别算,枚举到三层循环
✓ 对：a 等于 b 等价于 arr[i..k] 整段异或为 0,j 与取值无关
a 异或 b 正好把 arr[i..j-1] 和 arr[j..k] 两段拼成 arr[i..k] 的整段异或;只要它为 0,j 的位置只影响计数不影响判定
✗ 错：数三元组时漏算 j 的种数,一对只加 1
✓ 对：一段 arr[i..k] 异或为 0 时,j 有 k 减 i 种放法
j 要满足 i < j ≤ k,正好 k 减 i 个位置,每个都是一个合法三元组,不能只记一个
✗ 错：前缀配对用 q 减 p 当贡献
✓ 对：相等前缀对 (p, q) 贡献 q 减 p 减 1
这对对应 i = p、k = q 减 1,j 的种数是 k 减 i = q 减 p 减 1,多减的那个 1 别忘
完整代码（Python / C++ / Java）
Python
from __future__ import annotations
from typing import *
from collections import *
from functools import *
from itertools import *
from math import *
from heapq import *
from bisect import *
class Solution:
def countTriplets(self, arr: List[int]) -> int:
ans, n = 0, len(arr)
for i, x in enumerate(arr):
s = x
for k in range(i + 1, n):
s ^= arr[k]
if s == 0:
ans += k - i
return ansC++
#include <algorithm>
#include <array>
#include <cctype>
#include <climits>
#include <cmath>
#include <deque>
#include <functional>
#include <iostream>
#include <limits>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
using namespace std;
class Solution {
public:
int countTriplets(vector<int>& arr) {
int ans = 0, n = arr.size();
for (int i = 0; i < n; ++i) {
int s = arr[i];
for (int k = i + 1; k < n; ++k) {
s ^= arr[k];
if (s == 0) {
ans += k - i;
}
}
}
return ans;
}
};Java
import java.util.*;
class Solution {
public int countTriplets(int[] arr) {
int ans = 0, n = arr.length;
for (int i = 0; i < n; ++i) {
int s = arr[i];
for (int k = i + 1; k < n; ++k) {
s ^= arr[k];
if (s == 0) {
ans += k - i;
}
}
}
return ans;
}
}复杂度
时间
O(n²)
n 是 arr 长度。参考代码外层枚举起点 i、内层让 k 向右滚动异或,两层循环共 O(n²);每步只做一次异或和一次判断,都是 O(1)
空间
O(1)
参考代码只用一个滚动变量 s 和答案累加,额外空间是常数。动画里画的前缀数组与位置面板是为讲清原理的教学辅助,不是算法必需
看不够？换成动画再走一遍
上面的推演每一步都对应一帧动画。点开交互动画版，能一步步看着 形成两个异或相等数组的三元组数目 的数据怎么变、指针怎么走，还能切 Python / Java / C++ 跟着练。
面试官可能追问
最朴素的做法是什么,为什么慢?+
最朴素是三层循环枚举 i、j、k,再分别算两段异或比较,光枚举就 O(n³),还要算异或,非常慢。第一层优化是发现 a 等于 b 等价于 arr[i..k] 整段异或为 0,这样 j 与判定无关,只剩枚举 i 和 k 两层,再用滚动变量维护区间异或,降到 O(n²)。
前缀异或在这里起什么作用,能不能再快?+
前缀异或把整段异或为 0 翻译成 pre[i] 等于 pre[k+1],也就是找 pre 里相等的两格。如果用哈希表记录每个前缀值出现过的位置个数与位置之和,扫一遍 pre 就能在 O(n) 时间累计所有相等对的贡献:对当前 q,贡献等于前面同值个数乘以 q 减 1 再减去它们的位置之和。这样时间能从 O(n²) 进一步降到 O(n),代价是 O(n) 的哈希空间。
相等前缀对 (p, q) 为什么贡献 q 减 p 减 1,而不是 q 减 p?+
这对对应 i 等于 p、k 等于 q 减 1。三元组要求 i < j ≤ k,合法的 j 个数是 k 减 i,代进去就是 q 减 1 减 p,等于 q 减 p 减 1。直觉上,两格之间夹着的元素个数就是 j 的可选数,端点处会少一个,所以要多减 1。
想听吴师兄把这道题讲给你听？
文字版和动画都随便看。开通图解算法年卡，可以听吴师兄声线把 形成两个异或相等数组的三元组数目 一步步讲透（全站 0 节语音精讲，持续扩充）， 卡住的地方还有 AI 私教小欧就着动画帮你拆到懂。
本平台为独立第三方培训机构，与华为技术有限公司无任何关联；课程的服务内容与权益以购买协议为准，学习效果因个人情况而异。「华为 OD」「华为可信」等仅为对岗位与考试方向的客观描述，相关商标归各自权利人所有。