按位与为零的三元组

难度: Hard

给你一个整数数组 nums ，返回其中 按位与三元组 的数目。

按位与三元组 是由下标 (i, j, k) 组成的三元组，并满足下述全部条件：

0 <= i < nums.length
0 <= j < nums.length
0 <= k < nums.length
nums[i] & nums[j] & nums[k] == 0 ，其中 & 表示按位与运算符。

示例 1：

输入：nums = [2,1,3]
输出：12
解释：可以选出如下 i, j, k 三元组：
(i=0, j=0, k=1) : 2 & 2 & 1
(i=0, j=1, k=0) : 2 & 1 & 2
(i=0, j=1, k=1) : 2 & 1 & 1
(i=0, j=1, k=2) : 2 & 1 & 3
(i=0, j=2, k=1) : 2 & 3 & 1
(i=1, j=0, k=0) : 1 & 2 & 2
(i=1, j=0, k=1) : 1 & 2 & 1
(i=1, j=0, k=2) : 1 & 2 & 3
(i=1, j=1, k=0) : 1 & 1 & 2
(i=1, j=2, k=0) : 1 & 3 & 2
(i=2, j=0, k=1) : 3 & 2 & 1
(i=2, j=1, k=0) : 3 & 1 & 2

示例 2：

输入：nums = [0,0,0]
输出：27

提示：

1 <= nums.length <= 1000
0 <= nums[i] < 2¹⁶

Submission

运行时间: 191 ms

内存: 16.6 MB

class Solution:
    def countTriplets(self, nums: List[int]) -> int:
        u = 1
        for x in nums:
            while u <= x:
                u <<= 1
        cnt = [0] * u
        cnt[0] = len(nums)  # 直接统计空集
        for m in nums:
            m ^= u - 1
            s = m
            while s:  # 枚举 m 的非空子集
                cnt[s] += 1
                s = (s - 1) & m
        return sum(cnt[x & y] for x in nums for y in nums)

Explain

该题解采用了一种利用位运算的技巧来解决问题。首先找到数组中最大的数，并确定一个足够大的二进制数u，使得u是第一个大于数组中任何数的2的幂。这是为了方便后续的位运算。然后，使用一个数组cnt来记录每个可能的位模式（直到u-1）在数组中出现的次数。对于每个数m，在数组nums中，先计算其补码（m^=u-1），然后枚举其所有可能的非空子集，并更新cnt数组。最后，通过双重循环遍历nums数组，使用cnt数组计算所有满足条件的(i, j, k)三元组数量。具体来说，对于每对数x和y，寻找在cnt数组中x与y按位与的结果作为索引的值，这个值即表示有多少个k使得nums[k]与x和y按位与的结果为0。

时间复杂度: O(n*u + n^2)

空间复杂度: O(u + n)

class Solution:
    def countTriplets(self, nums: List[int]) -> int:
        u = 1
        for x in nums:
            while u <= x:
                u <<= 1  # 找到大于所有元素的最小2的幂
        cnt = [0] * u
        cnt[0] = len(nums)  # 初始化cnt数组，考虑所有元素为0的情况
        for m in nums:
            m ^= u - 1  # 计算每个数的补码
            s = m
            while s:  # 枚举m的所有非空子集
                cnt[s] += 1
                s = (s - 1) & m  # 更新到下一个子集
        return sum(cnt[x & y] for x in nums for y in nums)  # 双重循环计算所有满足条件的组合

Explore

选择变量u为大于数组中任何数的最小的2的幂主要是为了简化计算和优化性能。首先，这样做可以确保所有数都可以在u的位宽内表示，这对后续的位运算（如补码计算和子集枚举）是必要的。其次，使用2的幂作为边界可以使得位运算（如左移、按位与）更为高效，因为这些操作在计算机内部是优化过的。此外，这种选择使得数组cnt的大小刚好足够覆盖所有可能的位模式，从而避免了不必要的内存使用和计算复杂度。

在算法中，计算每个数的补码（使用`m ^= u - 1`）是为了将原始数据转换为一种形式，使得后续可以通过枚举子集来找到所有可能的位模式，这些位模式在与其他数进行按位与操作后可能产生零结果。这个转换实际上是将原始数值进行按位取反操作，但限定在u的位宽内。这样做的目的是为了便于使用子集枚举算法，直接得到补码对应的所有子集，从而简化查找过程。

在算法中，利用位操作` s = (s - 1) & m`来枚举一个数m的所有非空子集，是一种高效的子集枚举技术。这个操作的原理是：`s - 1`操作会将数s的二进制表示中最低位的1变为0，并将此1右边的所有0变为1。接下来的`& m`操作保证了只考虑那些原始数m中为1的位。这种方法通过逐步减少s的最低位的1，并应用与m的按位与，能够依次访问从m的最大子集到最小子集的所有非空子集，直到s为0停止。这确保了所有有效的子集被枚举出来，而不遗漏任何一个。