题目描述
思路解析动画文字版
记牢这条主线:a 等于 b 就是 arr[i..k] 整段异或为 0,再用前缀异或把它翻译成 pre[i] 等于 pre[k+1],也就是在 pre 里找相等的两格。下面每一帧都在套这条线。
阶段一 · 准备建前缀异或：上面这排是 arr = [2, 3, 1, 6, 7]。右边面板是要建的前缀异或数组 pre,它比 arr 多一格,一共 6 格,现在全是问号。第一格 pre[0] 我们约定等于 0,它代表一段什么都不异或的空区间,异或上 0 谁都不变,这个起点待会儿很有用。
阶段一 · 先看二进制：异或是按二进制位算的,先把每个数写成三位二进制看清:2 是 010,3 是 011,1 是 001,6 是 110,7 是 111。两个数异或时逐位比较,这一位相同得 0、不同得 1,各位互不影响。心里有了这张表,后面建前缀、判断整段是否为 0 都顺。
阶段一 · pre[0] = 0：先把 pre[0] 写成 0,它表示前 0 个数的异或,也就是什么都不异或,结果是 0。0 是异或的零元,谁异或 0 都等于它自己。正因如此,等会儿从下标 0 开头的区间,左端落在 pre[0] 上特别好处理。
阶段一 · 算 pre[1]：把 arr[0] = 2 接进来。新的前缀值 pre[1] 等于上一格 pre[0] = 0 再异或这个 2,二进制是 000 异或 010 等于 010,也就是 2。记到 pre[1] 这一格。
阶段一 · 算 pre[2]：把 arr[1] = 3 接进来。新的前缀值 pre[2] 等于上一格 pre[1] = 2 再异或这个 3,二进制是 010 异或 011 等于 001,也就是 1。记到 pre[2] 这一格。
阶段一 · 算 pre[3]：把 arr[2] = 1 接进来。新的前缀值 pre[3] 等于上一格 pre[2] = 1 再异或这个 1,二进制是 001 异或 001 等于 000,也就是 0。记到 pre[3] 这一格。
阶段一 · 算 pre[4]：把 arr[3] = 6 接进来。新的前缀值 pre[4] 等于上一格 pre[3] = 0 再异或这个 6,二进制是 000 异或 110 等于 110,也就是 6。记到 pre[4] 这一格。
阶段一 · 算 pre[5]：把 arr[4] = 7 接进来。新的前缀值 pre[5] 等于上一格 pre[4] = 6 再异或这个 7,二进制是 110 异或 111 等于 001,也就是 1。记到 pre[5] 这一格。
阶段一完成 · pre 数组：前缀异或数组建好了,从左到右是 0、2、1、0、6、1。从这一帧起,舞台上摆的就是这排 pre,原来的 arr 退到幕后。记住每格含义:pre[t] 是 arr 前 t 个数的异或,比如 pre[3] = 0 就是 arr[0] 异或 arr[1] 异或 arr[2]。
阶段二 · 整段异或为 0 的信号：先看一个具体例子体会转化。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,这正是我们要找的信号。
阶段二 · 一对相等前缀贡献几个：把规律说清:在 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 上从左到右扫,边扫边配对。
扫描 · pre[0] = 0 首次出现：扫到第 0 格,pre[0] = 0。查一下前面的记录,这个值之前没出现过,所以暂时配不成对,把它的位置 0 记进面板,继续往后扫。答案目前还是 0。
扫描 · pre[1] = 2 首次出现：扫到第 1 格,pre[1] = 2。查一下前面的记录,这个值之前没出现过,所以暂时配不成对,把它的位置 1 记进面板,继续往后扫。答案目前还是 0。
扫描 · pre[2] = 1 首次出现：扫到第 2 格,pre[2] = 1。查一下前面的记录,这个值之前没出现过,所以暂时配不成对,把它的位置 2 记进面板,继续往后扫。答案目前还是 0。
扫描 · pre[3] = 0 命中：扫到第 3 格,pre[3] = 0。面板里这个值之前在位置 0 出现过,绿色这几格就是相等前缀,正好配成对。每一对都意味着中间夹着一段整段异或为 0 的区间,下一帧来数它们各贡献几个三元组。
扫描 · 结算贡献(答案 2)：逐对结算:(0, 3) 贡献 3 减 0 减 1 = 2。意思是 i 取 0、k 取 2,中间的 j 各有那么多种放法。把贡献加进答案,现在累计是 2。算完别忘了把当前位置 3 也记进面板,因为它以后可能再和更靠右的相等格配对。
扫描 · pre[4] = 6 首次出现：扫到第 4 格,pre[4] = 6。查一下前面的记录,这个值之前没出现过,所以暂时配不成对,把它的位置 4 记进面板,继续往后扫。答案目前还是 2。
扫描 · pre[5] = 1 命中：扫到第 5 格,pre[5] = 1。面板里这个值之前在位置 2 出现过,绿色这几格就是相等前缀,正好配成对。每一对都意味着中间夹着一段整段异或为 0 的区间,下一帧来数它们各贡献几个三元组。
扫描 · 结算贡献(答案 4)：逐对结算:(2, 5) 贡献 5 减 2 减 1 = 2。意思是 i 取 2、k 取 4,中间的 j 各有那么多种放法。把贡献加进答案,现在累计是 4。通用扫描里会把当前位置也记进面板,不过本例已经到最后一格,不会再产生新配对。
完成 · 答案 4：扫完整排 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 翻译成两格相等,一遍扫描就数完。
边界先想清:单元素凑不出三元组答案 0、两个相等数异或为 0 给 1 个、整段异或为 0 时按 j 的种数算(这里 2 个)。
面试重点:朴素 O(n³) 到双循环 O(n²) 再到哈希前缀 O(n);相等前缀对贡献是 q 减 p 减 1,因为 j 的合法个数是 k 减 i。
参考代码
from __future__ import annotationsfrom 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 ans复杂度
- 时间：O(n²)，n 是 arr 长度。参考代码外层枚举起点 i、内层让 k 向右滚动异或,两层循环共 O(n²);每步只做一次异或和一次判断,都是 O(1)
- 空间：O(1)，参考代码只用一个滚动变量 s 和答案累加,额外空间是常数。动画里画的前缀数组与位置面板是为讲清原理的教学辅助,不是算法必需
易错点
面试追问把动画讲成自己的话
追问最朴素的做法是什么,为什么慢?
追问前缀异或在这里起什么作用,能不能再快?
追问相等前缀对 (p, q) 为什么贡献 q 减 p 减 1,而不是 q 减 p?
这道题到这就讲完了。动画和文字是同一套思路——别光看，关掉页面自己默写一遍。然后顺着主线继续：
每个查询的最大异或值
LeetCode 1829 · 中等 · 沿着 字典树套路 继续往下推进
把这道题真正学会，再走
图解算法年卡 ¥99 /年
- ✓本题每步动画的吴师兄语音讲解（全站陆续覆盖）
- ✓小欧带 8 步通关训练——追问到不看答案也能写对、能 30 秒讲给面试官听
- ✓学习报告，记录每道题的掌握程度
76k+ GitHub Star · 吴师兄开源图解算法，几十万开发者在看的算法讲解
想成体系刷透这类套路？去图解算法专题