1. 问题分析与暴力解法

1.1 题目重述与理解

LeetCode 982题要求我们统计数组中满足特定条件的三元组数量。具体来说，给定一个整数数组nums，我们需要找出所有满足nums[i] & nums[j] & nums[k] == 0的三元组(i,j,k)的数量，其中&表示按位与操作。

按位与操作的特点是：对于每一位，只有当所有操作数的该位都为1时，结果的该位才为1，否则为0。因此，三元组的按位与结果为0意味着对于每一位，至少有一个数字的该位为0。

1.2 暴力解法实现

最直观的解法是三重循环枚举所有可能的三元组：

public int countTripletsBruteForce(int[] nums) { int count = 0; int n = nums.length; for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { for (int k = 0; k < n; k++) { if ((nums[i] & nums[j] & nums[k]) == 0) { count++; } } } } return count; }

这种解法的时间复杂度是O(n³)，当n=1000时，运算量将达到10亿次，显然无法在合理时间内完成。

注意：在实际编程竞赛或面试中，即使能写出暴力解法，也应该立即思考优化方案，而不是满足于这种低效的实现。

2. 优化思路与数学原理

2.1 按位与运算的性质

按位与运算有几个重要性质：

1. 交换律：a & b = b & a
2. 结合律：(a & b) & c = a & (b & c)
3. 幂等性：a & a = a

这些性质意味着我们可以重新组合运算顺序，而不影响最终结果。特别地，我们可以将问题转化为先计算nums[i] & nums[j]，再与nums[k]进行与运算。

2.2 预处理思路

基于上述性质，我们可以分两步解决问题：

1. 预处理阶段：计算所有nums[i] & nums[j]的结果，并统计每个结果出现的频率
2. 统计阶段：对于每个nums[k]，找出所有与它按位与为0的预处理结果，累加对应的频率

这种方法的优势在于将O(n³)的问题分解为O(n²)的预处理和O(n×2^m)的统计阶段，其中m是数字的二进制位数。

2.3 位运算优化技巧

关键优化点在于如何高效找到所有满足mask & nums[k] == 0的mask。这等价于mask是~nums[k]的子集（考虑指定位数）。我们可以使用位运算技巧高效枚举这些子集：

int mask = ~nums[k] & ((1 << 16) - 1); // 假设使用16位表示 int subset = mask; do { // 处理subset count += freq.getOrDefault(subset, 0); subset = (subset - 1) & mask; } while (subset != mask); // 处理完所有子集后会回到mask

这种方法可以避免检查所有可能的mask值，大幅提高效率。

3. 详细实现与代码解析

3.1 预处理阶段实现

预处理阶段需要计算所有数对的按位与结果：

Map<Integer, Integer> freq = new HashMap<>(); for (int a : nums) { for (int b : nums) { int key = a & b; freq.put(key, freq.getOrDefault(key, 0) + 1); } }

这里使用HashMap来存储每个按位与结果出现的次数。选择HashMap而不是数组是因为按位与结果可能很稀疏，使用数组会浪费大量空间。

3.2 统计阶段实现

统计阶段需要处理每个数字，并查找与之按位与为0的所有预处理结果：

int count = 0; for (int num : nums) { int mask = (~num) & 0xFFFF; // 使用16位表示 int subset = mask; do { count += freq.getOrDefault(subset, 0); subset = (subset - 1) & mask; } while (subset != mask); }

这里0xFFFF是16位全1的掩码，确保我们只考虑低16位。对于大多数实际问题，16位已经足够，因为数字范围通常不会太大。

3.3 完整代码实现

结合上述两部分，完整的解决方案如下：

import java.util.HashMap; import java.util.Map; public class Solution { public int countTriplets(int[] nums) { // 预处理阶段：计算所有a & b的频率 Map<Integer, Integer> freq = new HashMap<>(); for (int a : nums) { for (int b : nums) { int key = a & b; freq.put(key, freq.getOrDefault(key, 0) + 1); } } // 统计阶段：对于每个c，统计满足(a&b)&c==0的三元组 int count = 0; for (int num : nums) { int mask = (~num) & 0xFFFF; // 取反并限制在16位 int subset = mask; do { count += freq.getOrDefault(subset, 0); subset = (subset - 1) & mask; } while (subset != mask); } return count; } }

4. 复杂度分析与优化验证

4.1 时间复杂度分析

1. 预处理阶段：双重循环遍历所有数对，时间复杂度O(n²)
2. 统计阶段：外层循环O(n)，内层循环取决于num的二进制表示中0的数量。最坏情况下（num=0），需要遍历所有2^16=65536种可能，因此总时间复杂度为O(n² + n×2^m)

对于n=1000，m=16的情况：

• n² = 1,000,000
• n×2^m ≈ 65,000,000 总操作量约6600万次，比暴力解法的10亿次提高了约15倍。

4.2 空间复杂度分析

空间复杂度主要来自存储按位与结果的频率表。最坏情况下，所有数对按位与结果都不同，空间复杂度为O(n²)。但实际上由于按位与操作会减少置位数量，实际空间消耗会小很多。

4.3 实际性能测试

我们对比暴力解法和优化解法在不同输入规模下的表现：

可以看到，随着n增大，优化解法的优势越来越明显。对于小规模输入，优化解法可能稍慢，这是因为预处理和哈希表操作的开销。

5. 边界条件与特殊案例

5.1 全零数组

当数组中所有元素都是0时，任何三元组的按位与结果都是0。此时结果应该是n³。我们的优化解法也能正确处理这种情况，因为0 & 0 = 0，且~0 & 0xFFFF = 0xFFFF，会统计所有可能的数对组合。

5.2 大数情况

当数组中的数很大（如接近2³¹-1）时，需要注意：

1. 确保位运算不会溢出（Java中int是32位有符号数）
2. 可能需要调整掩码位数。如果数字确实很大，可以将0xFFFF改为0xFFFFFFFF，但会显著增加运行时间

5.3 稀疏数组

当数组中大部分数字为0时，按位与结果也会大量为0。此时频率表中0的计数会很高，而其他值的计数很少。我们的解法能自动适应这种情况，因为子集枚举会快速收敛。

6. 进一步优化方向

6.1 位宽自适应

可以根据数组中最大数字的位数动态调整掩码位数：

int maxNum = 0; for (int num : nums) maxNum = Math.max(maxNum, num); int bitWidth = 32 - Integer.numberOfLeadingZeros(maxNum); int mask = (~num) & ((1 << bitWidth) - 1);

这样可以减少不必要的位数处理，提高效率。

6.2 并行计算

预处理阶段的双重循环可以并行化，因为每个数对的计算是独立的。在Java中可以使用并行流：

Map<Integer, Integer> freq = new HashMap<>(); IntStream.range(0, nums.length).parallel().forEach(i -> { int a = nums[i]; for (int b : nums) { int key = a & b; synchronized (freq) { freq.put(key, freq.getOrDefault(key, 0) + 1); } } });

注意需要同步对频率表的访问。

6.3 替代数据结构

对于密集的按位与结果，使用数组可能比HashMap更高效：

int maxMask = (1 << 16) - 1; int[] freq = new int[maxMask + 1]; for (int a : nums) { for (int b : nums) { freq[a & b]++; } }

这会增加空间使用，但减少哈希计算的开销。

7. 类似问题与扩展思考

7.1 类似LeetCode问题

1. 问题318：最大单词长度乘积 - 同样使用位掩码和预处理技巧
2. 问题187：重复的DNA序列 - 使用位运算高效处理字符串
3. 问题137：只出现一次的数字II - 位运算统计特定位的出现次数

7.2 扩展问题

如果问题改为四元组或k元组，该如何解决？例如，统计nums[i] & nums[j] & nums[k] & nums[l] == 0的四元组数量。

解决方案思路类似：

1. 预处理所有三元组的按位与结果和频率
2. 对于每个nums[l]，统计满足条件的预处理结果
3. 时间复杂度将变为O(n³ + n×2^m)，空间复杂度O(n³)

7.3 实际应用场景

这类位运算技巧在以下场景有实际应用：

1. 数据库中的位图索引
2. 网络协议中的标志位处理
3. 图形学中的颜色通道操作
4. 嵌入式系统的寄存器配置

掌握这些技巧可以大幅提高处理二进制数据的效率。