# 982. Triples with Bitwise AND Equal To Zero 按位与为零的三元组

@TOC

## # 题目描述

Given an array of integers `A`, find the number of triples of indices (i, j, k) such that:

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

Example 1:

``````Input: [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
``````

Note:

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

## # 解题方法

``````class Solution {
public:
int countTriplets(vector<int>& A) {
const int N = A.size();
int res = 0;
unordered_map<int, int> m_;
for (int i = 0; i < N; ++i) {
for (int j = 0; j < N; ++j) {
++m_[(A[i] & A[j])];
}
}
for (int i = 0; i < N; ++i) {
for (auto a : m_) {
if ((A[i] & a.first) == 0)
res += a.second;
}
}
return res;
}
};
``````

## # 日期

2019 年 1 月 27 日 —— 这个周赛不太爽