四至五月学习笔记

学习笔记

力扣 982 按位与为零的三元组

思路：暴力枚举
先枚举一二个数，再看第三个数是否满足条件
前者是O(n^2)

unordered_map<int, int> cnt; // 记录每个数出现的次数
for (int i = 0; i < n; ++i) {
    for (int j = i + 1; j < n; ++j) {
        cnt[arr[i] & arr[j]]++; // 记录每个数出现的次数
    }
}

然后用一个循环遍历所有可能的数，看是否满足条件，并且找到每个数的补码集合

for (int i:arr){
    int mask = i^((1<<16)-1); // 找到补码,因为数据最大是16位，所以补码是1<<16-1
    int sub = mask;
    do{
        ans += cnt[sub];
        sub = (sub-1)&mask; // 找到补码集合, 当sub = -1 是取补集会回到mask 
    }while(sub!=mask);// 找到补码集合, 当sub = -1 是取补集会回到mask
}