LeetCode 982. 位运算三元组等于零

982. Triples with Bitwise AND Equal To Zero

Given an integer array nums, return the number of AND triples.

An AND triple is a triple of indices (i, j, k) such that:

• 0 <= i < nums.length
• 0 <= j < nums.length
• 0 <= k < nums.length
• nums[i] & nums[j] & nums[k] == 0, where & represents the bitwise-AND operator.

示例 1

Input: nums = [2,1,3] Output: 12 Explanation: We could choose the following i, j, k triples: (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

Input: nums = [0,0,0] Output: 27

约束条件

• 1 <= nums.length <= 1000
• 0 <= nums[i] < 2^16

解题思路

• 预计算所有成对按位与结果 nums[i] & nums[j] 并统计每个结果出现的次数。
• 对于固定的 nums[k]，需要 (nums[i] & nums[j]) & nums[k] == 0。
• 这意味着 (nums[i] & nums[j]) 只能在 nums[k] 为 0 的位上使用 1。
• 构建 freeMask = ~nums[k]（限制在 16 位）以表示允许的位。
• 枚举 freeMask 的所有子掩码，并从预计算的表中累加它们的频率。
• 对每个 k 求和得到有效的 (i, j, k) 三元组总数。

代码实现

int countTriplets(int* nums, int numsSize) {
    static int cnt[1 << 16]; // reset (static keeps memory; must clear each call)
    for (int i = 0; i < (1 << 16); i++) cnt[i] = 0;
    // count all pairwise AND results
    for (int i = 0; i < numsSize; i++) {
        for (int j = 0; j < numsSize; j++) {
            cnt[nums[i] & nums[j]]++;
        }
    }
    long long ans = 0;
    for (int k = 0; k < numsSize; k++) {
        int freeMask = (~nums[k]) & 0xFFFF; // bits that can be 1 in (a&b) while still ANDing to 0 with nums[k]
        int sub = freeMask;
        while (1) {
            ans += cnt[sub];
            if (sub == 0) break;
            sub = (sub - 1) & freeMask; // iterate all submasks
        }
    }
    return (int)ans;
}