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

Categories:

题目描述
思路分析
1. 解法一：哈希表预处理（推荐）
2. 解法二：枚举子集优化
相似题目

题目描述

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

思路分析

解法一：哈希表预处理（推荐）

核心思路：

枚举三元组 (i, j, k) 满足 nums[i] & nums[j] & nums[k] == 0，暴力三重循环为 O(n³)，需要优化。

预处理阶段：用哈希表 andCount 记录所有两两按位与的结果及其出现次数，即 andCount[nums[i] & nums[j]]++，时间复杂度 O(n²)。

枚举阶段：对每个 nums[k]，遍历 andCount 中所有键值对，若 key & nums[k] == 0，则累加对应的出现次数。

整体时间复杂度从 O(n³) 降至 O(n² + n × C)，其中 C 为哈希表大小（最多 2¹⁶ = 65536）。

复杂度分析：

时间复杂度：O(n² + n × C)，其中 n 为数组长度，C 为不同按位与结果的数量（最多 65536）

空间复杂度：O(C)，哈希表存储两两按位与的结果

class Solution {
    public int countTriplets(int[] nums) {
        // 预处理：统计所有两两按位与的结果及次数
        Map<Integer, Integer> andCount = new HashMap<>();
        for (int a : nums) {
            for (int b : nums) {
                int key = a & b;
                andCount.merge(key, 1, Integer::sum);
            }
        }

        int result = 0;

        // 枚举第三个数，查找与之按位与为零的两元组
        for (int c : nums) {
            for (Map.Entry<Integer, Integer> entry : andCount.entrySet()) {
                if ((entry.getKey() & c) == 0) {
                    result += entry.getValue();
                }
            }
        }

        return result;
    }
}

func countTriplets(nums []int) int {
    // 预处理：统计所有两两按位与的结果及次数
    andCount := make(map[int]int)
    for _, a := range nums {
        for _, b := range nums {
            andCount[a&b]++
        }
    }

    result := 0

    // 枚举第三个数，查找与之按位与为零的两元组
    for _, c := range nums {
        for key, cnt := range andCount {
            if key&c == 0 {
                result += cnt
            }
        }
    }

    return result
}

解法二：枚举子集优化

核心思路：

利用位运算的性质：a & b & c == 0 等价于 c 是 ~(a & b) 的子集。

预处理数组中每个值出现的次数 freq，再用 SOS（Sum over Subsets）DP 预处理超集和。

对每对 (i, j)，计算 mask = ~(nums[i] & nums[j])，利用预处理的超集表快速得到满足条件的 nums[k] 数量。

复杂度分析：

时间复杂度：O(n² + C × logC)，其中 C = 65536

空间复杂度：O(C)

class Solution {
    public int countTriplets(int[] nums) {
        int maxVal = 1 << 16;

        // 统计每个值的出现次数
        int[] freq = new int[maxVal];
        for (int num : nums) {
            freq[num]++;
        }

        // SOS DP：f[mask] 表示是 mask 子集的元素总个数
        int[] f = freq.clone();
        for (int i = 0; i < 16; i++) {
            for (int mask = 0; mask < maxVal; mask++) {
                if ((mask >> i & 1) == 1) {
                    f[mask] += f[mask ^ (1 << i)];
                }
            }
        }

        int result = 0;

        // 枚举前两个数，利用预处理结果统计第三个数
        for (int a : nums) {
            for (int b : nums) {
                int complement = (~(a & b)) & (maxVal - 1);
                result += f[complement];
            }
        }

        return result;
    }
}

func countTriplets(nums []int) int {
    maxVal := 1 << 16

    // 统计每个值的出现次数
    freq := make([]int, maxVal)
    for _, num := range nums {
        freq[num]++
    }

    // SOS DP：f[mask] 表示是 mask 子集的元素总个数
    f := make([]int, maxVal)
    copy(f, freq)
    for i := 0; i < 16; i++ {
        for mask := 0; mask < maxVal; mask++ {
            if mask>>i&1 == 1 {
                f[mask] += f[mask^(1<<i)]
            }
        }
    }

    result := 0

    // 枚举前两个数，利用预处理结果统计第三个数
    for _, a := range nums {
        for _, b := range nums {
            complement := (^(a & b)) & (maxVal - 1)
            result += f[complement]
        }
    }

    return result
}

相似题目

题目	难度	考察点
201. 数字范围按位与	中等	位运算
318. 最大单词长度乘积	中等	位运算、哈希表
421. 数组中两个数的最大异或值	中等	位运算、字典树
898. 子数组按位或操作	中等	位运算、动态规划
1835. 所有数对按位与结果的异或和	困难	位运算
1863. 找出所有子集的异或总和再求和	简单	位运算、枚举

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2023/63091914