Leetcode每日一题 —— 3514. 不同 XOR 三元组的数目 II

魔法师 2026-07-24 09:05 1

思路

第一反应就是模拟，看数据量应该没问题。

先将原数组两两异或并记录

将第一步得到的结果与原数组异或得到最终记录

最终记录的数量即为结果

一开始用的HashSet，超时了，应该是结构和冲突高的缘故，改为boolean[]就快了。

代码

class Solution {

    public int uniqueXorTriplets(int[] nums) {

        int n = nums.length;

        int o = Arrays.stream(nums).max().orElse(0);

        int mx = 1 << (32 - Integer.numberOfLeadingZeros(o));

        boolean[] set = new boolean[mx];

        boolean[] res = new boolean[mx];

        for (int i = 0; i < n; i++) {

            int a = nums[i];

            for (int j = i + 1; j < n; j++) {

                set[a ^ nums[j]] = true;

            }

            res[a] = true;

        }

        for (int i = 1; i < mx; i++) {

            if (set[i]) {

                for (int num : nums) {

                    res[num ^ i] = true;

                }

            }

        }

        int ans = 0;

        for (int i = 0; i < mx; i++) {

            if (res[i]) {

                ans++;

            }

        }

        return ans;

    }

}

附TLE的版本

class Solution {

    public int uniqueXorTriplets(int[] nums) {

        int n = nums.length;

        HashSet<Integer> set = new HashSet<>();

        HashSet<Integer> res = new HashSet<>();

        for (int i = 0; i < n; i++) {

            int a = nums[i];

            for (int j = i + 1; j < n; j++) {

                set.add(a ^ nums[j]);

            }

            res.add(a);

        }

        for (int a : nums) {

            for (int num : set) {

                res.add(num ^ a);

            }

        }

        return res.size();

    }

}

最新回复 (2)

SomeBottle 07-24 09:27

1楼

虽然输入规模减小了，但是 O(n^3) 级别还是无法接受的。可以先枚举所有成对异或值，用哈希表标记，然后枚举哈希表和第三个值再进行异或计算。因为数值最大才 1500，近乎 O(n^2) 是可以接受的。

class Solution {

public:

    int uniqueXorTriplets(vector<int>& nums) {

        // 这回 nums 不是 1...n 的排列了

        // nums 输入规模变小了，但是 O(n^3) 级别还是无法接受的

        

        // 先找到 nums 中最大值

        int n=nums.size();

        int maxVal=nums[0];

        for(int num:nums){

            maxVal=max(maxVal,num);

        }

        int bitWidth=bit_width((unsigned int)maxVal); // 找到有效二进制位的宽度

        maxVal=1<<bitWidth; // 再怎么异或也不可能大于等于 2^bit_width

        // 先枚举两个数的异或，标记所有存在的两数异或

        vector<bool> pairXors(maxVal,false);

        for(int i=0;i<n;i++){

            for(int j=i;j<n;j++){

                pairXors[nums[i]^nums[j]]=true;

            }

        }

        // 然后再计算和标记三个一组的 XOR

        int res=0;

        vector<bool> triXors(maxVal,false);

        // 枚举所有出现的两数异或值，再枚举第三个数来计算

        for(int num=0;num<maxVal;num++){

            if(!pairXors[num]){

                continue;

            }

            // 这里不需要考虑顺序，前面已经算出来的一对可以是 i j, 可以是 i k 也可以是 j k

            for(int k=0;k<n;k++){

                if(triXors[num^nums[k]]){

                    continue;

                }

                triXors[num^nums[k]]=true;

                res++;

            }

        }

        return res;

    }

};

Infinity4B 07-24 09:47

2楼

思考半天发现好像还是无脑计算

算术评级6 第 154 场双周赛 Q3 难度分1884

class Solution:

    def uniqueXorTriplets(self, nums: List[int]) -> int:

        xor_set = set()

        n = len(nums)

        for i in range(n):

            for j in range(i,n):

                xor_res = nums[i] ^ nums[j]

                xor_set.add(xor_res)

        res_res = set()

        for i in range(n):

            for item in xor_set:

                xor_res = nums[i] ^ item

                res_res.add(xor_res)

        return len(res_res)

* 帖子来源Linux.do

附近帖子

↑qwen3.8 Max优惠平台
↑求seedance2.0/2.5稳定的中转站/上游
↑大佬们，有没有什么好用的语义模型推荐？
↑求助，grok4.5突然道德感飙升怎么回事
↑求助佬，咨询一下为什么我CF的worker被全部删除了
📍 Leetcode每日一题 —— 3514. 不同 XOR 三元组的数目 II
↓佬们都是用什么ssh工具管理服务器的
↓佬友们对于屎山代码是选择重写还是重构捏
↓现在最接近claude那种人味的是啥模型？
↓显卡涨价刚拉开序幕？
↓微软E5开发者计划大缩水，Onedrive中的文件怎么样低成本地转移到其他地方呢？