982. 按位与为零的三元组 (Hard)

问题描述

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;
    }
};