LeetCode1442:形成两个异或相等数组的三元组数目

一、题目描述

二、示例

三、条件限制

四、解题思路及代码

4.1 三重循环

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution:
def countTriplets(self, arr: List[int]) -> int:
n = len(arr)
s = [0]
for val in arr:
s.append(s[-1] ^ val)

ans = 0
for i in range(n):
for j in range(i + 1, n):
for k in range(j, n):
if s[i] == s[k + 1]:
ans += 1
return ans

4.2 二重循环

当等式 \(S_i=S_{k+1}\) 成立时,\([i+1,k]\) 的范围内任意 \(j\) 都是符合要求的, 对应的三元组个数为 \(k-i\) ,因此只需枚举 \(i\)\(k\)

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution:
def countTriplets(self, arr: List[int]) -> int:
n = len(arr)
s = [0]
for val in arr:
s.append(s[-1] ^ val)

ans = 0
for i in range(n):
for k in range(i + 1, n):
if s[i] == s[k + 1]:
ans += k - i
return ans