# 1442. Count Triplets That Can Form Two Arrays of Equal XOR

{% embed url="<https://leetcode.com/problems/count-triplets-that-can-form-two-arrays-of-equal-xor/>" %}

要找 i, j, k，直接brute-force做的话，到k这里就已经iterate 2遍，但因为计算a/b值的时候又要循环2次，最后时间复杂度应该在O(n\*\*4)级别，该题会TLE，所以要想办法降低运行时间。

```python
class Solution:
    # O(n**4)
    def countTriplets(self, arr: List[int]) -> int:
        count = 0
        for i in range(len(arr)-1):
            for j in range(i+1, len(arr)):
                for k in range(j, len(arr)):
                    a, b = 0, 0
                    for t in range(i, j):
                        a ^= arr[t]
                    for t in range(j, k+1):
                        b ^= arr[t]
                    if a == b:
                        count += 1
        return count
```

直觉上循环 i, j, k 还是得做的，直接看能不能降低 a/b 的计算成本，利用 xor 的一个性质：

![](https://1821609058-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-M74fKaD-4PpYzUZfdEf%2F-M8YpyPdwsOsHI7cR_iR%2F-M8Ys5_WPC6MQySNF9fn%2Fimage.png?alt=media\&token=fe7c6781-9d05-4980-a749-d37514170c02)

这样只需要提前遍历一遍 array，把xors计算出来，然后在里面按index找 a/b 就可以了，总体上少循环一层，可以控制时间复杂度在O(n\*\*3)，但为了存储xors，空间复杂度到了O(n)，提交通过。

```python
class Solution:
    # O(n**3)
    def countTriplets(self, arr: List[int]) -> int:
        count = 0
        xors = [0]
        for n in range(0, len(arr)):
            xors.append(xors[n]^arr[n])
        for i in range(len(arr)-1):
            for j in range(i+1, len(arr)):
                for k in range(j, len(arr)):
                    a = xors[i] ^ xors[j]
                    b = xors[j] ^ xors[k+1]
                    if a == b: count+=1
        return count
```

做上面这个方法的时候，就可以在性质公式里看出，A\[0]^...A\[j] 的大小与中间点 i 的取值完全没关系，或者说，i 和 k 找到的时候，j取中间任意的值，都可以满足 a==b 的条件。

这里可按先找 i 再找 k 然后找 j 来写，找到第一个 j 的时候就意味着 i->k 的所有值都是有效的 j 解。或者，再利用一个性质 (a = b) => (a^b = 0) 来简化，把问题变成找 (i, k) 使得 xors\[i] == xors\[k+1].

![问题就变成了](https://1821609058-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-M74fKaD-4PpYzUZfdEf%2F-M8YpyPdwsOsHI7cR_iR%2F-M8Ytphnd_bele-hznRk%2Fimage.png?alt=media\&token=e9720ca9-bd52-4599-a4a2-6a99c5cf94f6)

![](https://1821609058-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-M74fKaD-4PpYzUZfdEf%2F-M8YpyPdwsOsHI7cR_iR%2F-M8YtsYDDwwLq_EUyJe1%2Fimage.png?alt=media\&token=e5c0886b-e8d6-4d3e-b5dd-3450d7c98da3)

这样又再少了一层对 j 的搜索，时间复杂度降到 O(n\*\*2).

```python
class Solution:
    # O(n**2)
    def countTriplets(self, arr: List[int]) -> int:
        count = 0
        xors = [0]
        for n in range(0, len(arr)):
            xors.append(xors[n]^arr[n])
        for i in range(0, len(arr)-1):
            for k in range(i+1, len(arr)):
                if xors[i] == xors[k+1]: count+=(k-i)
        return count
```

其实还有个用 target sum 的方法，可以降到 O(n) 复杂度，但俺没写出来。
