题目描述

给定一个整数数组 A，找到三元组 (i, j, k) 的个数，使得

• 0 <= i < A.length
• 0 <= j < A.length
• 0 <= k < A.length
• A[i] & A[j] & A[k] == 0，其中 & 表示按位与操作。

样例

输入：[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

注意

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

算法

(哈希表) $O(n^2 + nm)$

1. 枚举 $i$ 和 $j$，同时使用一个哈希表记录 A[i] & A[j] 的值所对应的个数。
2. 然后枚举哈希表，对于每一个值，再次遍历数组 A，对于合法的 A[k]，累加 A[i] & A[j] 的个数。

时间复杂度

• 假设 $m$ 为不同的 A[i] & A[j] 的个数，最多为 $2^{16}$ 个。
• 对于每个不同的 A[i] & A[j]，需要遍历一次数组寻找答案。
• 所以时间复杂度是 $O(n^2 + nm)$。

空间复杂度

• 需要 $O(m)$ 的额外空间存储哈希表。

C++ 代码

class Solution {
public:
    int countTriplets(vector<int>& A) {
        const int n = A.size();
        unordered_map<int, int> h;

        for (int i = 0; i < n; i++)
            for (int j = 0; j < n; j++)
                h[A[i] & A[j]]++;

        int ans = 0;
        for (const auto &[k, v]: h)
            for (int i = 0; i < n; i++)
                if ((A[i] & k) == 0)
                    ans += v;

        return ans;
    }
};