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

一、题目描述

二、示例

三、条件限制

四、解题思路及代码

4.1 三重循环

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$。

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