LeetCode 982. 按位与为零的三元组
题目描述
题意分析
统计满足
nums[i] & nums[j] & nums[k] == 0的下标三元组数量。三个下标分别独立选择，可以相同；交换下标位置后，只要三元组不同，就应单独计数。因此不能去重数组，也不能只枚举递增下标。直接枚举三个下标需要 $O(n^3)$ 时间。按位与满足结合律，后一个数只关心前两个数与出来的结果，可以先把有相同中间结果的数对合并计数。
解法：有序数对计数 + 第三个数匹配
核心思路
[!blue]
定义
cnt[mask]为满足nums[i] & nums[j] == mask的有序下标对数量。双层循环都遍历整个数组，包含i == j，也会分别统计(i, j)和(j, i)。虽然代码循环变量保存的是数值，但每个数组位置都会被访问，所以重复值对应的多个位置仍会增加各自的频次。固定第三个位置的值
c后，原条件变成mask & c == 0，即二者没有共同为1的二进制位。某个mask满足条件时，产生它的所有有序数对都能与当前第三个位置组成合法三元组，因此应增加整个cnt[mask]，而不是只增加一次。每个三元组都有唯一的第三个位置和唯一的前两数与结果，会被归入恰好一个这样的计数中；反过来，每次加入的数对与当前第三个位置都满足原条件。因此这种合并既不漏计，也不重复计算同一个下标三元组。
题目中的数都小于 $2^{16}$，两个数的与结果也只有低
16位，所以中间状态最多有 $2^{16}$ 种。哈希表只保存实际出现的结果，第三层搜索规模由不同mask的数量决定。
解题步骤
- 双层枚举全部有序对，累加按位与结果频次。
- 逐个枚举第三个数。
- 遍历已出现的 mask，按位与为零则加入对应频次。
- 返回总计数。
mask == 0可以与任意第三个数匹配；第三个数为零时，所有数对都能匹配。数组长度最多为1000，三元组总数最多是 $n^3 = 10^9$，答案及数对频次都能用int保存。
代码实现
class Solution {
public int countTriplets(int[] nums) {
// cnt[mask] = 有多少个有序对 (i, j) 满足 nums[i] & nums[j] == mask。
Map<Integer, Integer> cnt = new HashMap<>();
for (int a : nums) {
for (int b : nums) {
int mask = a & b;
cnt.put(mask, cnt.getOrDefault(mask, 0) + 1);
}
}
int answer = 0;
for (int c : nums) {
for (Map.Entry<Integer, Integer> e : cnt.entrySet()) {
// c 的每个 1 位都必须落在 mask 的 0 位上。
if ((e.getKey() & c) == 0) {
answer += e.getValue();
}
}
}
return answer;
}
}
func countTriplets(nums []int) int {
// cnt[mask] = 有多少个有序对 (i, j) 满足 nums[i] & nums[j] == mask。
cnt := make(map[int]int)
for _, a := range nums {
for _, b := range nums {
cnt[a&b]++
}
}
answer := 0
for _, c := range nums {
for mask, times := range cnt {
// c 的每个 1 位都必须落在 mask 的 0 位上。
if mask&c == 0 {
answer += times
}
}
}
return answer
}
复杂度分析
- 时间复杂度：期望 $O(n^2+nU)$，U 为实际出现的与结果数，$U≤min(n^2,2^{16})$。
- 空间复杂度：$O(U)$。
关键点总结
[!green]
- 归并的是相同中间结果，频次不能丢失。
- 有序对包含 i=j，不使用三数之和的去重方式。
- Java 判断位运算结果时需要将按位与表达式加括号。
易错点总结
[!yellow]
- 只枚举 i<j：漏掉反向顺序和相同下标。
- 匹配一个 mask 只加一：没有计入该结果对应的多个数对。
- 先将输入去重：重复位置仍应分别计数。
- 要求三个数中必须有零：例如 2、1、3 都非零，但三者按位与为零。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 454. 四数相加 II | 中等 | 同样先累计两项组合的结果频次，再匹配后半部分，本题组合运算是按位与而非加法。 |
转载与许可
许可
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！