当前位置：首页 > news >正文

LeetCode 982题解：位运算优化三元组计数问题

news 2026/8/13 4:54:53

1. 问题背景与核心挑战

今天遇到一道有趣的LeetCode题目（编号982），要求统计数组中满足特定条件的三元组数量。题目描述很简单：给定一个整数数组nums，返回满足nums[i] & nums[j] & nums[k] == 0的三元组(i, j, k)的数量，其中0 ≤ i, j, k < nums.length。

这个按位与操作的三元组问题看似直接，实则暗藏玄机。当我第一次看到这个题目时，脑海中立即浮现出几个关键疑问：

暴力解法的时间复杂度是多少？在数据量较大时是否可行？
按位与运算有哪些特性可以利用来优化？
是否存在某种数学规律或位运算技巧可以降低计算复杂度？

经过一番探索，我发现这个问题完美展示了位运算与算法优化的精妙结合。下面分享我的解题思路和最终实现的优化方案。

2. 暴力解法分析与复杂度评估

最直观的解法当然是三重循环暴力枚举：

public int countTriplets(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亿次，显然无法在合理时间内完成。在LeetCode上测试时，这个解法会直接超时。

提示：在实际面试中，即使你能想到优化方案，也应该先提出暴力解法并分析其复杂度，这展示了你的系统性思维。

3. 位运算特性与优化思路

3.1 按位与运算的基本性质

按位与(&)运算有几个重要特性：

任何数与0进行按位与运算结果都是0
按位与具有结合律：(a & b) & c = a & (b & c)
按位与的结果不会大于任一操作数

这些性质提示我们可以利用中间结果进行优化，避免重复计算。

3.2 关键优化思路：预计算两数组合

观察到三元组的按位与可以拆分为两步：

先计算nums[i] & nums[j]的所有可能结果
然后检查这些结果与nums[k]的按位与是否为0

这样我们可以将O(n³)的问题转化为O(n²) + O(n²)的问题。具体步骤：

预计算所有nums[i] & nums[j]的结果，存储它们的频率
对于每个预计算结果和每个nums[k]，检查它们的按位与是否为0
根据频率统计有效三元组数量

4. 优化实现与代码解析

基于上述思路，下面是优化后的Java实现：

public int countTriplets(int[] nums) { int maxNum = 1 << 16; // 题目中nums[i] < 2^16 int[] freq = new int[maxNum]; int n = nums.length; // 预计算所有nums[i] & nums[j]的频率 for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { freq[nums[i] & nums[j]]++; } } int count = 0; // 检查每个预计算结果与nums[k]的按位与 for (int k = 0; k < n; k++) { for (int m = 0; m < maxNum; m++) { if ((m & nums[k]) == 0) { count += freq[m]; } } } return count; }

4.1 复杂度分析

空间复杂度：O(2¹⁶)，用于存储频率数组
时间复杂度：O(n² + n*2¹⁶)
- 预计算阶段：O(n²)
- 统计阶段：O(n*2¹⁶)

虽然理论复杂度仍然较高，但在实际测试中这个解法能够通过LeetCode的所有测试用例，因为2¹⁶=65536是一个固定常数。

5. 进一步优化：位掩码技巧

我们可以利用位运算的性质进一步优化内层循环：

public int countTriplets(int[] nums) { int maxNum = 1 << 16; int[] freq = new int[maxNum]; int n = nums.length; for (int num : nums) { for (int num2 : nums) { freq[num & num2]++; } } int count = 0; for (int num : nums) { int mask = num ^ 0xFFFF; // 取反操作 int subset = mask; do { count += freq[subset]; subset = (subset - 1) & mask; } while (subset != mask); } return count; }

这个优化利用了位掩码的枚举技巧，将内层循环从遍历所有可能的m改为只遍历与nums[k]按位与为0的那些m。这种方法在最坏情况下复杂度相同，但在实际运行中通常更快。

6. 边界条件与测试用例

在实现这类位运算问题时，特别需要注意边界条件：

空数组输入：应该返回0
单个元素数组：如果元素为0，返回1(0&0&0=0)；否则返回0
全0数组：任何三元组都满足条件，返回n³
全1数组：只有所有元素按位与才为1，不满足条件，返回0

测试用例示例：

@Test public void testCountTriplets() { Solution solution = new Solution(); assertEquals(12, solution.countTriplets(new int[]{2, 1, 3})); assertEquals(27, solution.countTriplets(new int[]{0, 0, 0})); assertEquals(0, solution.countTriplets(new int[]{1, 1, 1})); assertEquals(1, solution.countTriplets(new int[]{0})); assertEquals(0, solution.countTriplets(new int[]{1})); }