982. 按位与为零的三元组（位运算）

题目

• https://leetcode.cn/problems/triples-with-bitwise-and-equal-to-zero/description/?orderBy=most_votes

思路

• 参考灵神题解，非常易懂，总结一些方法
• 状态压缩常用找下 x 的一个子集（关于1）：\(for(s = x;s;s = (s - 1) & x)\)(再加上一个全0的情况)
• 上面的时间复杂度接近\(x^2\)的，所以先对任意两个数字的与hash会超时，但是换一个方向容易发现n是很小的
• 所以先找一个数字二进制补集的子集，然后再枚举任意两个数字的与，累加

代码

class Solution {
public:
    int countTriplets(vector<int>& nums) {
		int n = nums.size();
		int bit1[1 << 16] = {0};

        bit1[0] = nums.size();
		for(auto x:nums)
        {
            int s = x ^ ((1 << 16) - 1);
			for(int y = s;y;y = (y - 1) & s)
				bit1[y] ++;
        }
		
		int ans = 0;
		for(auto x:nums)
			for(auto y:nums)
				ans += bit1[x&y];
		return ans;
		
    }
};