按位与为零的三元组--哈希表优化循环

Manda ·

更新时间:2024-11-13

· 952 次阅读

0x01.问题

给定一个整数数组 A，找出索引为 (i, j, k) 的三元组，使得：
0 <= i < A.length 0 <= j < A.length 0 <= k < A.length A[i] & A[j] & A[k] == 0，其中 & 表示按位与（AND）操作符。
输入示例：[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

C++函数形式为 int countTriplets(vector& A) 0x02.分析

三元组进行按位与，正常思路肯定是要三层循环，但是细看一下A的范围，到达了1000，如果三层循环，肯定超时，所以我们必须优化一下。

用三层循环的目的就是保证每三个数都能进行一次按位与操作，我们可不可以先计算出两个与操作的值，再对每个数，与这两个的值进行按位与操作呢？

肯定是可以的，但需要记录下每两个按位与产生的值出现的频率，因为这是和次数挂钩的。

我们可以用一个哈希表记录每两个按位与操作产生的值的数量，再用一个哈希表记录每个元素出现的数量，这样就可以避免重复操作。

这样，三层循环就变成了两层循环。

0x03.解决代码

class Solution {
public:
    int countTriplets(vector& A) {
        unordered_map map1;
        unordered_map map2;
        for(int n:A) map1[n]++;
        for(int i=0;i<A.size();i++){
            for(int j=0;j<A.size();j++){
                map2[A[i] & A[j]]++;
            }
        }
        int ans=0;
        for(auto p1:map1){
            for(auto p2:map2){
                if((p1.first & p2.first)==0){
                    ans+=p1.second*p2.second;
                }
            }
        }
        return ans;
    }
};

ATFWUS --Writing By 2020–03–20

作者：如颖随心-＞A

三元组循环哈希表三元哈希优化元组