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

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³)当n1000时循环次数将达到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(0000)否则返回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})); }7. 同类问题与扩展思考这类按位运算的组合计数问题在编程竞赛中很常见。类似的问题包括按位或为零的三元组计数按位异或为特定值的三元组计数子数组按位与/或/异或的统计解决这类问题的通用思路是分析位运算的性质寻找可以预计算的中间结果利用位掩码技巧优化枚举过程考虑分治或按位处理的策略对于更大的数据规模如n10⁵可能需要更高级的数据结构或数学方法如快速沃尔什变换(FWT)等。