问题描述 链接到标题

982. 按位与为零的三元组 (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¹⁶

解题思路 链接到标题

可以先用哈希表ump存储nums[i] & nums[j]的结果，再与nums[k]按位与，如果结果为0，res += ump[nums[i] & nums[j]]。

优化，我们把二进制看成集合，二进制从低到高第i位为1表示i在集合中，为0表示i不在集合中，例如$a = 1101_{(2)}$表示集合$A={0,2,3}$；

那么，$a & b = 0$即集合$A$和集合$B$没有交集，或者说$B$是集合$\complement_U A$，这里$U={0,1,2,…,15}$，对应的数字即$0xffff$，一个数异或$0xffff$就能得到这个数的补集；

所以，代码可以优化成枚举$m = nums[k]\oplus 0xffff$的子集；

要枚举$m$的子集$s$，可以将$s$从$m$不断减一直到0，如果$s & m = s$，说明$s$是$m$的子集；

更高效的做法是直接“跳到”下一个子集，即$s$更新为$(s - 1)& m$，这样做的正确性在于，$s-1$只把$s$最低位的$1$改成了$0$（考虑$s$对应的集合），比这个$1$更低的$0$全都变成了$1$，因此下一个子集，一定是$s-1$的子集，直接$&m$，就能得到下一个子集；

最后，当$s=0$时，由于$-1$的二进制全为$1$，所有$(s-1)&m = m$，所以我们可以判断下一个子集是否又回到$m$，来判断是否要退出循环。

注：这一技巧常用于子集状态压缩DP中

代码 链接到标题 

class Solution {
public:
    int countTriplets(vector<int> &nums) {
        int cnt[1 << 16]{};
        for (int x : nums)
            for (int y : nums)
                ++cnt[x & y];
        int ans = 0;
        for (int m : nums) {
            m ^= 0xffff;
            int s = m;
            do { // 枚举 m 的子集（包括空集）
                ans += cnt[s];
                s = (s - 1) & m;
            } while (s != m);
        }
        return ans;
    }
};