1.题目基本信息
1.1.题目描述
给你一个整数数组 nums ，返回其中 按位与三元组 的数目。
按位与三元组 是由下标 (i, j, k) 组成的三元组，并满足下述全部条件：
0 <= i < nums.length
0 <= j < nums.length
0 <= k < nums.length
nums[i] & nums[j] & nums[k] == 0 ，其中 & 表示按位与运算符。
1.2.题目地址
https://leetcode.cn/problems/triples-with-bitwise-and-equal-to-zero/description/
2.解题方法
2.1.解题思路
二进制子集及操作
知识点：
求补集方法：假如全集为u，则b=a^u为a关于全集u的补集。
枚举二进制子集方法：枚举m的非空子集，记子集s=m，迭代s=(s-1)&m，其中&m是为了排除s-1时出现的非m子集情况。
2.2.解题步骤
第一步，统计比nums中所有数字都大的单1数字u，u-1对应全集
第二步，求nums中各个元素的二进制集合补集的子集，并统计个数，记为数组cnts（长度为u）
2.1.求num关于u-1的补集m
2.2.求m的各个子集，并将个数合并到cnts中；当子集s==0时，(s-1)&m==m，此时while循环退出
第三步，从nums中进行两两枚举x,y，统计cnts[x&y]的和，即为题解
3.解题代码
python代码
class Solution:
def countTriplets(self, nums: List[int]) -> int:
# 思路：二进制子集及操作
# 知识点：求补集方法：假如全集为u，则b=a^u为a关于全集u的补集。枚举二进制子集方法：枚举m的非空子集，记子集s=m，迭代s=(s-1)&m，其中&m是为了排除s-1时出现的非m子集情况。
# 第一步，统计比nums中所有数字都大的单1数字u，u-1对应全集
u = 1
for num in nums:
while num >= u:
u <<= 1
# 第二步，求nums中各个元素的二进制集合补集的子集，并统计个数，记为数组cnts（长度为u）
cnts = [0] * u
for num in nums:
# 2.1.求num关于u-1的补集m
m = num ^ (u - 1)
# 2.2.求m的各个子集，并将个数合并到cnts中；当子集s==0时，(s-1)&m==m，此时while循环退出
s = m
while True:
cnts[s] += 1
s = (s - 1) & m
if s == m:
break
# 第三步，从nums中进行两两枚举x,y，统计cnts[x&y]的和，即为题解
return sum([sum([cnts[x & y] for y in nums]) for x in nums])
4.执行结果
