LeetCode 题解工作台
形成两个异或相等数组的三元组数目
给你一个整数数组 arr 。 现需要从数组中取三个下标 i 、 j 和 k ，其中 (0 。 a 和 b 定义如下： a = arr[i] ^ arr[i + 1] ^ ... ^ arr[j - 1] b = arr[j] ^ arr[j + 1] ^ ... ^ arr[k] 注意： ^ 表示 …
5
题型
6
代码语言
3
相关题
当前训练重点
中等 · 数组·哈希·扫描
答案摘要
根据题目描述，要找到满足 $a = b$ 的三元组 $(i, j, k)$，即满足 $s = a \oplus b = 0$，我们只需要枚举左端点 ，然后计算以 为右端点的区间 $[i, k]$ 的前缀异或和 ，如果 $s = 0$，那么对于任意 $j \in [i + 1, k]$，都满足 $a = b$，即 $(i, j, k)$ 是一个满足条件的三元组，一共有 $k - i$ 个，我们将其…
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 数组·哈希·扫描 题型思路
题目描述
给你一个整数数组 arr 。
现需要从数组中取三个下标 i、j 和 k ，其中 (0 <= i < j <= k < arr.length) 。
a 和 b 定义如下：
a = arr[i] ^ arr[i + 1] ^ ... ^ arr[j - 1]b = arr[j] ^ arr[j + 1] ^ ... ^ arr[k]
注意：^ 表示 按位异或 操作。
请返回能够令 a == b 成立的三元组 (i, j , k) 的数目。
示例 1：
输入：arr = [2,3,1,6,7] 输出：4 解释：满足题意的三元组分别是 (0,1,2), (0,2,2), (2,3,4) 以及 (2,4,4)
示例 2：
输入：arr = [1,1,1,1,1] 输出：10
示例 3：
输入：arr = [2,3] 输出：0
示例 4：
输入：arr = [1,3,5,7,9] 输出：3
示例 5：
输入：arr = [7,11,12,9,5,2,7,17,22] 输出：8
提示：
1 <= arr.length <= 3001 <= arr[i] <= 10^8
解题思路
方法一：枚举
根据题目描述，要找到满足 的三元组 ，即满足 ，我们只需要枚举左端点 ，然后计算以 为右端点的区间 的前缀异或和 ，如果 ，那么对于任意 ，都满足 ，即 是一个满足条件的三元组，一共有 个，我们将其累加到答案中即可。
枚举结束后，返回答案即可。
时间复杂度 ，其中 是数组 的长度。空间复杂度 。
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) |
| 空间 | O(n) |
面试官常问的追问
外企场景- question_mark
Focus on prefix XOR computation to compare subarrays quickly.
- question_mark
Consider hash map accumulation to avoid triple nested loops.
- question_mark
Watch for overlapping subarrays and proper index handling.
常见陷阱
外企场景- error
Forgetting that XOR of a subarray arr[i..j] can be computed using prefix XOR in O(1).
- error
Miscounting triplets when multiple previous prefix XOR values exist at different indices.
- error
Incorrectly handling i, j, k constraints leading to invalid subarrays.
进阶变体
外企场景- arrow_right_alt
Count quadruplets where splitting arr into three consecutive subarrays yields equal XORs.
- arrow_right_alt
Find all subarrays of length >= 2 with XOR zero without restricting to triplets.
- arrow_right_alt
Modify the array to allow negative numbers and still count valid triplets.