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

发表于 更新于 分类于 阅读次数： 本文字数： 529 阅读时长 ≈ 1 分钟

一、题目描述

二、示例

三、条件限制

四、解题思路及代码

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