leetcode 982. 按位与为零的三元组

题解

分两步,先计算 A[i] & A[j] 保存出现的次数,再计算 (A[i] & A[j]) & A[k] 判断是否为零

示例代码(go)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
func countTriplets(A []int) int {
res, n := 0, len(A)
hash := make(map[int]int)
for i := 0; i < n; i++ {
for j := 0; j < n; j++ {
hash[A[i] & A[j]]++
}
}
for key, count := range hash {
for k := 0; k < n; k++ {
if key & A[k] == 0 {
res += count
}
}
}
return res
}