Hard

题目描述

给你一个下标从 0 开始的整数数组 nums 和两个整数 low 和 high，返回 好数对 的数目。

好数对 是一个数对 (i, j) ，其中 0 <= i < j < nums.length 且 low <= (nums[i] XOR nums[j]) <= high。

示例 1：

输入：nums = [1,4,2,7], low = 2, high = 6
输出：6
解释：所有好数对 (i, j) 如下：
    - (0, 1): nums[0] XOR nums[1] = 5 
    - (0, 2): nums[0] XOR nums[2] = 3
    - (0, 3): nums[0] XOR nums[3] = 6
    - (1, 2): nums[1] XOR nums[2] = 6
    - (1, 3): nums[1] XOR nums[3] = 3
    - (2, 3): nums[2] XOR nums[3] = 5

示例 2：

输入：nums = [9,8,4,2,1], low = 5, high = 14
输出：8
解释：所有好数对 (i, j) 如下：
​​​​​    - (0, 2): nums[0] XOR nums[2] = 13
    - (0, 3): nums[0] XOR nums[3] = 11
    - (0, 4): nums[0] XOR nums[4] = 8
    - (1, 2): nums[1] XOR nums[2] = 12
    - (1, 3): nums[1] XOR nums[3] = 10
    - (1, 4): nums[1] XOR nums[4] = 9
    - (2, 3): nums[2] XOR nums[3] = 6
    - (2, 4): nums[2] XOR nums[4] = 5

提示：

  • 1 <= nums.length <= 2 * 10^4
  • 1 <= nums[i] <= 2 * 10^4
  • 1 <= low <= high <= 2 * 10^4

解题思路

解题思路

这道题要求统计数组中所有数对的异或值在指定区间内的数量。暴力解法是O(n²)枚举所有数对，但时间复杂度较高。

核心思想：转换问题

  • 要求异或值在 [low, high] 区间内的数对数量
  • 可以转换为：异或值 ≤ high 的数对数量 - 异或值 ≤ (low-1) 的数对数量
  • 这样问题就简化为：如何快速统计异或值小于等于某个值 K 的数对数量

Trie（字典树）解法：

  1. 将数字按二进制位构建 Trie 树
  2. 对于每个数字，在 Trie 中查找与它异或后结果小于等于 K 的数字个数
  3. 从高位到低位遍历，根据当前位的值决定搜索方向

具体步骤：

  • 建立一个二进制 Trie，每个节点记录经过该节点的数字个数
  • 对每个数字 x，查询与 x 异或后结果 ≤ K 的数字个数
  • 递归搜索 Trie，当前位如果可以选择使结果更小的路径，就累加该路径下的所有数字

这种方法时间复杂度为 O(n log max_val)，比暴力解法更优。

代码实现

class Solution {
private:
    struct TrieNode {
        TrieNode* children[2];
        int count;
        
        TrieNode() {
            children[0] = children[1] = nullptr;
            count = 0;
        }
    };
    
    TrieNode* root;
    
    void insert(int num) {
        TrieNode* node = root;
        for (int i = 14; i >= 0; i--) {
            int bit = (num >> i) & 1;
            if (!node->children[bit]) {
                node->children[bit] = new TrieNode();
            }
            node = node->children[bit];
            node->count++;
        }
    }
    
    int countPairsWithXorLessOrEqual(int num, int limit) {
        TrieNode* node = root;
        int result = 0;
        
        for (int i = 14; i >= 0; i--) {
            if (!node) break;
            
            int numBit = (num >> i) & 1;
            int limitBit = (limit >> i) & 1;
            
            if (limitBit == 1) {
                // 可以选择与当前位相同的路径，这样XOR结果为0，肯定小于limit
                if (node->children[numBit]) {
                    result += node->children[numBit]->count;
                }
                // 继续搜索与当前位不同的路径
                node = node->children[1 - numBit];
            } else {
                // 只能选择与当前位相同的路径
                node = node->children[numBit];
            }
        }
        
        return result;
    }
    
public:
    int countPairs(vector<int>& nums, int low, int high) {
        root = new TrieNode();
        int result = 0;
        
        for (int num : nums) {
            result += countPairsWithXorLessOrEqual(num, high);
            result -= countPairsWithXorLessOrEqual(num, low - 1);
            insert(num);
        }
        
        return result;
    }
};

class Solution:
    def countPairs(self, nums: List[int], low: int, high: int) -> int:
        class TrieNode:
            def __init__(self):
                self.children = [None, None]
                self.count = 0
        
        def insert(root, num):
            node = root
            for i in range(14, -1, -1):
                bit = (num >> i) & 1
                if not node.children[bit]:
                    node.children[bit] = TrieNode()
                node = node.children[bit]
                node.count += 1
        
        def count_pairs_with_xor_less_or_equal(root, num, limit):
            node = root
            result = 0
            
            for i in range(14, -1, -1):
                if not node:
                    break
                
                num_bit = (num >> i) & 1
                limit_bit = (limit >> i) & 1
                
                if limit_bit == 1:
                    if node.children[num_bit]:
                        result += node.children[num_bit].count
                    node = node.children[1 - num_bit]
                else:
                    node = node.children[num_bit]
            
            return result
        
        root = TrieNode()
        result = 0
        
        for num in nums:
            result += count_pairs_with_xor_less_or_equal(root, num, high)
            result -= count_pairs_with_xor_less_or_equal(root, num, low - 1)
            insert(root, num)
        
        return result

public class Solution {
    public class TrieNode {
        public TrieNode[] children = new TrieNode[2];
        public int count = 0;
    }
    
    private void Insert(TrieNode root, int num) {
        TrieNode node = root;
        for (int i = 14; i >= 0; i--) {
            int bit = (num >> i) & 1;
            if (node.children[bit] == null) {
                node.children[bit] = new TrieNode();
            }
            node = node.children[bit];
            node.count++;
        }
    }
    
    private int CountPairsWithXorLessOrEqual(TrieNode root, int num, int limit) {
        TrieNode node = root;
        int result = 0;
        
        for (int i = 14; i >= 0; i--) {
            if (node == null) break;
            
            int numBit = (num >> i) & 1;
            int limitBit = (limit >> i) & 1;
            
            if (limitBit == 1) {
                if (node.children[numBit] != null) {
                    result += node.children[numBit].count;
                }
                node = node.children[1 - numBit];
            } else {
                node = node.children[numBit];
            }
        }
        
        return result;
    }
    
    public int CountPairs(int[] nums, int low, int high) {
        TrieNode root = new TrieNode();
        int result = 0;
        
        foreach (int num in nums) {
            result += CountPairsWithXorLessOrEqual(root, num, high);
            result -= CountPairsWithXorLessOrEqual(root, num, low - 1);
            Insert(root, num);
        }
        
        return result;
    }
}

var countPairs = function(nums, low, high) {
    class TrieNode {
        constructor() {
            this.children = {};
            this.count = 0;
        }
    }
    
    class Trie {
        constructor() {
            this.root = new TrieNode();
        }
        
        insert(num) {
            let node = this.root;
            for (let i = 14; i >= 0; i--) {
                const bit = (num >> i) & 1;
                if (!node.children[bit]) {
                    node.children[bit] = new TrieNode();
                }
                node = node.children[bit];
                node.count++;
            }
        }
        
        countXorLessThan(num, limit) {
            let node = this.root;
            let count = 0;
            
            for (let i = 14; i >= 0; i--) {
                if (!node) break;
                
                const numBit = (num >> i) & 1;
                const limitBit = (limit >> i) & 1;
                
                if (limitBit === 1) {
                    if (node.children[numBit]) {
                        count += node.children[numBit].count;
                    }
                    node = node.children[1 - numBit];
                } else {
                    node = node.children[numBit];
                }
            }
            
            return count;
        }
    }
    
    const trie = new Trie();
    let result = 0;
    
    for (let num of nums) {
        result += trie.countXorLessThan(num, high + 1) - trie.countXorLessThan(num, low);
        trie.insert(num);
    }
    
    return result;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度大小
时间复杂度O(n × log(max_val))
空间复杂度O(n × log(max_val))

其中 n 是数组长度，max_val 是数组中的最大值。由于题目限制数值在 2×10⁴ 以内，所以 log(max_val) ≈ 15。

相关题目