题目

给你一个整数数组 nums （下标 从 0 开始 计数）以及两个整数：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⁴
• 1 <= nums[i] <= 2 * 10⁴
• 1 <= low <= high <= 2 * 10⁴

思路

字典树

解法

class Solution {
    // 字典树思路: 要获得异或值在区间[low, high]的所有对数;
    // 可以把数值按照顺序，以二进制的形式从高位到低位插入到字典树中，并且记录每个二进制前缀出现的次数;
    // 前缀树中可以获得 <= x的 所有数值的数量，因此可以使用 f(high) - f(low - 1); 获得该区间的值的数量
    // 前置知识：两个数的比较，就要从高到低比较每个二进制位;直到一方为1 一方为0，为1的一方更大，如果到达末尾都一模一样,说明两个数是相同的。
    
    class Trie { // 字典树结点
        Trie[] child; 
        int sum; 
        public Trie () { // 初始化Trie结点
            child = new Trie[2]; // 分别记录二进制位的0和1;
            sum = 0; // 记录当前二进制前缀出现了多少次
        }
    }

    private Trie root = null; // 字典树的根;
    private static final int DEPTH = 14; // 字典树最大的深度

    public int countPairs(int[] nums, int low, int high) {
        int ans = 0;
        root = new Trie(); // 给字典树初始化
        // 依次插入每一个数值; 后面插入的数值，就可以和前面的数值比较;
        for (int i = 1; i < nums.length; ++i) {
            insert(nums[i - 1]);
            ans += get(nums[i], high) - get(nums[i], low - 1);
        }
        return ans;
    }

    // 把数字k的二进制形式，按高到低位依次插入到字典树中;
    public void insert(int k) {
        Trie node = this.root; // 获取字典树
        for (int i = DEPTH; i >= 0; --i) {
            int bit = (k >> i) & 1; // 取数字k的第i个二进制位;
            if (node.child[bit] == null) { // 如果这个位置没有值，就创建一个结点，表示bit这个位出现了
                node.child[bit] = new Trie(); 
            }
            node = node.child[bit]; // 进入到字典树下一层;
            node.sum++; // 记录当前前缀出现的次数。
        }
    }

    // 此时前缀树中已插入了一些数值，此get函数可获得满足n 与这些数值的异或 <= k的对数;
    // 字典树中的child数组，如果存在值，就代表对应二进制存在; 例如child[0]存在，表示这一层的二进制0是出现过的
    // 注意：sum 保存的是之前出现的二进制的前缀们;
    public int get(int n, int k) {
        int sum = 0; // 记录出现了多少对 异或值 <= k;
        Trie node = this.root; // 获得字典树
        for (int i = DEPTH; i >= 0; --i) { // 从高位往地位取二进制位。
            int bitn = (n >> i) & 1; // 取数值n的第i个二进制位;
            int bitk = (k >> i) & 1; // 取数值k的第i个二进制位;
            if (bitk == 1) { 
                // 如果bitk == 1，那么 在字典树中的二进制位只有与bitn相同，才能使二进制的异或等于0
                // 那就看bitn相同的二进制位是否出现过，如果出现过，说明和bitn的异或等于0，小于bitk的1;
                // 记录即可。
                if (node.child[bitn] != null) {
                    sum += node.child[bitn].sum;
                } 
                // bitn ^ 1，表示与bitn相反的二进制位， 如果与bitn相反的不存在，那就意味着字典树
                // 中没有二进制位能够与bitn异或使得结果等于1，此时n与字典树中的值的异或都小于k;
                if (node.child[bitn ^ 1] == null) {
                    return sum;
                }
                node = node.child[bitn ^ 1]; // 否则的话，就继续进入下一层判断;
            } else {
                // 如果字典树中该层的二进制和bitn相同的二进制不存在，就说明不存在异或 == 0，即
                // 不存在 == bitk的情况，那么就可以直接返回了;
                if (node.child[bitn] == null) {                        
                    return sum;
                }
                // 如果存在，继续进入下一层比较。
                node = node.child[bitn];
            }
        }
        sum += node.sum; // 如果字典树中的数值与n的异或，存在等于k的情况，就会来到字典树的末尾；
        return sum;
    }
}

总结

• 分析出几种情况，然后分别对各个情况实现