982. 按位与为零的三元组

题目链接：982. 按位与为零的三元组

方法一：枚举（超时）

解题思路

直接枚举\(i, j, k\)分别取\([0, n-1]\)，判断\((\)\(nums[i]\) & \(nums[j]\) & \(nums[k]\)\()\) \(==\) \(0\)。由于本题的数量级较大 \(n = 1000\)，\(n^3 = 10^9\)，会导致暴力枚举超时。
注意：\(==\) 的优先级大于 \(&\)，所以对于 \(&\) 运算要加\(()\)。

代码

class Solution {
public:
    int countTriplets(vector<int>& nums) {
        int cnt[ 1 << 16 ]{};
        cnt[0] = nums.size();
        for (auto m : nums) {
            m ^= 0xffff;
            for (int s = m; s ; s = (s - 1) & m) {
                cnt[s] ++ ;
            }
        }
        int ans = 0;
        for (auto x : nums) {
            for (auto y : nums) {
                ans += cnt[x & y];
            }
        }
        return ans;
    }
};

方法二：枚举 + 预处理

解题思路

对于\(nums[i]\) & \(nums[j]\)的值\(y\)进行计数，然后\(nums[k]\)再与\(y\)进行与运算。

代码

class Solution {
public:
    int countTriplets(vector<int>& nums) {
        int cnt[ 1 << 16 ]{};
        for (auto i : nums) {
            for (auto j : nums)
            cnt[i ^ j] ++ ;
        }
        int ans = 0;
        for (auto x : nums) {
            for (int y = 0; y < 1 << 16; y ++ ) {
                if ((x & y) == 0) ans += cnt[y];
            }
        }
        return ans;
    }
};

复杂度分析

时间复杂度：\(O(n(n + U))，n = nums.length()\)；
空间复杂度：\(O(m)，m = max(nums)\)。

方法三：枚举 + 子集优化

解题思路

参考—灵茶山艾府：有技巧的枚举 + 常数优化（Python/Java/C++/Go）

代码

class Solution {
public:
    int countTriplets(vector<int>& nums) {
        int cnt[ 1 << 16 ]{};
        cnt[0] = nums.size();
        for (auto m : nums) {
            m ^= 0xffff;
            for (int s = m; s ; s = (s - 1) & m) {
                cnt[s] ++ ;
            }
        }
        int ans = 0;
        for (auto x : nums) {
            for (auto y : nums) {
                ans += cnt[x & y];
            }
        }
        return ans;
    }
};

复杂度分析

时间复杂度：\(O(n(n + U))，n = nums.length()\)；
空间复杂度：\(O(m)，m = max(nums)\)。