Hard

题目描述

给定一个整数数组 nums，返回 AND 三元组的数量。

AND 三元组是索引三元组 (i, j, k) 满足：

  • 0 <= i < nums.length
  • 0 <= j < nums.length
  • 0 <= k < nums.length
  • nums[i] & nums[j] & nums[k] == 0，其中 & 表示按位与运算符。

示例 1：

输入：nums = [2,1,3]
输出：12
解释：我们可以选择以下 i, j, k 三元组：
(i=0, j=0, k=1) : 2 & 2 & 1
(i=0, j=1, k=0) : 2 & 1 & 2
(i=0, j=1, k=1) : 2 & 1 & 1
(i=0, j=1, k=2) : 2 & 1 & 3
(i=0, j=2, k=1) : 2 & 3 & 1
(i=1, j=0, k=0) : 1 & 2 & 2
(i=1, j=0, k=1) : 1 & 2 & 1
(i=1, j=0, k=2) : 1 & 2 & 3
(i=1, j=1, k=0) : 1 & 1 & 2
(i=1, j=2, k=0) : 1 & 3 & 2
(i=2, j=0, k=1) : 3 & 2 & 1
(i=2, j=1, k=0) : 3 & 1 & 2

示例 2：

输入：nums = [0,0,0]
输出：27

约束条件：

  • 1 <= nums.length <= 1000
  • 0 <= nums[i] < 2^16

解题思路

这道题要求找到所有满足三个数按位与为0的索引三元组数量。

方法一：暴力枚举（O(n³)） 最直接的方法是三重循环枚举所有可能的 (i,j,k) 组合，检查 nums[i] & nums[j] & nums[k] 是否为0。

方法二：优化枚举（推荐） 考虑到按位与的性质：(a & b) & c = 0，我们可以先计算所有 nums[i] & nums[j] 的结果，然后对每个结果统计出现次数。接着枚举每个 nums[k]，检查有多少个预计算的结果与其按位与为0。

具体步骤：

  1. 使用哈希表记录所有 nums[i] & nums[j] 的值及其出现次数
  2. 对于每个 nums[k]，遍历哈希表，累加所有与 nums[k] 按位与为0的结果对应的次数

这样将时间复杂度从 O(n³) 优化到 O(n² + n×m)，其中 m 是不同的两数按位与结果数量，最多为 2^16。

由于数组元素范围在 [0, 2^16)，两数按位与的结果也在此范围内，所以哈希表大小是有限的。

代码实现

class Solution {
public:
    int countTriplets(vector<int>& nums) {
        unordered_map<int, int> count;
        int n = nums.size();
        
        // 计算所有 nums[i] & nums[j] 的值及其出现次数
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                count[nums[i] & nums[j]]++;
            }
        }
        
        int result = 0;
        // 对于每个 nums[k]，统计满足条件的三元组数量
        for (int k = 0; k < n; k++) {
            for (auto& [val, cnt] : count) {
                if ((val & nums[k]) == 0) {
                    result += cnt;
                }
            }
        }
        
        return result;
    }
};

class Solution:
    def countTriplets(self, nums: List[int]) -> int:
        from collections import defaultdict
        
        count = defaultdict(int)
        n = len(nums)
        
        # 计算所有 nums[i] & nums[j] 的值及其出现次数
        for i in range(n):
            for j in range(n):
                count[nums[i] & nums[j]] += 1
        
        result = 0
        # 对于每个 nums[k]，统计满足条件的三元组数量
        for k in range(n):
            for val, cnt in count.items():
                if (val & nums[k]) == 0:
                    result += cnt
        
        return result

public class Solution {
    public int CountTriplets(int[] nums) {
        var count = new Dictionary<int, int>();
        int n = nums.Length;
        
        // 计算所有 nums[i] & nums[j] 的值及其出现次数
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                int val = nums[i] & nums[j];
                count[val] = count.GetValueOrDefault(val, 0) + 1;
            }
        }
        
        int result = 0;
        // 对于每个 nums[k]，统计满足条件的三元组数量
        for (int k = 0; k < n; k++) {
            foreach (var kvp in count) {
                if ((kvp.Key & nums[k]) == 0) {
                    result += kvp.Value;
                }
            }
        }
        
        return result;
    }
}

var countTriplets = function(nums) {
    const n = nums.length;
    const pairAnd = new Map();
    
    for (let i = 0; i < n; i++) {
        for (let j = 0; j < n; j++) {
            const andResult = nums[i] & nums[j];
            pairAnd.set(andResult, (pairAnd.get(andResult) || 0) + 1);
        }
    }
    
    let count = 0;
    for (let k = 0; k < n; k++) {
        for (const [pairResult, freq] of pairAnd) {
            if ((pairResult & nums[k]) === 0) {
                count += freq;
            }
        }
    }
    
    return count;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型大小
时间复杂度O(n² + n×m)，其中 n 是数组长度，m 是不同的两数按位与结果数量，最多为 2^16
空间复杂度O(m)，哈希表存储两数按位与结果及其出现次数