一、问题描述
给定一个数组。三个索引
- i，i ~ [0, array.length)
- j, j ~ [0, array.length)
- k, k ~ [0, array.length)
求有多少种组合方式使得 array[i] & array[j] & array[k] = 0?
二、思路
用缓存存储遍历过的结果
三、Code
package algorithm;
import java.util.Arrays;
/**
* Created by adrian.wu on 2019/2/27.
*/
public class CountTriplets {
public int countTriplets(int[] A) {
int n = A.length, res = 0;
int[] vd = new int[(1 << 16)];
Arrays.fill(vd, -1);
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
int ijAnd = A[i] & A[j];
if (vd[ijAnd] == -1) {
vd[ijAnd] = 0;
for (int k = 0; k < n; k++) {
if ((ijAnd & A[k]) == 0) vd[ijAnd]++;
}
}
res += vd[ijAnd];
}
}
return res;
}
}