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

Loading...LeetCode

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

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 的一个性质：

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

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].

问题就变成了

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

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) 复杂度，但俺没写出来。