数组中是否存在三数异或为0？O(N²)复杂度解法问询

思路1：哈希集合预处理两两异或结果 #

• 先遍历数组里所有两两元素对(i,j)，计算x_i ⊕ x_j，把结果存到哈希集合里。
• 接着遍历数组每个元素x_k，检查x_k是否在这个集合里。要是存在，就说明有满足条件的三元组。
• 时间复杂度：两两异或的计算是O(N²)次操作，每次异或是常数时间（不管是32位还是64位数值，位数固定），哈希集合的插入、查询平均都是O(1)，所以整体是O(N²)，完全符合作业要求。
• 注意：如果题目允许i,j,k重复（比如i=j），这个方法直接能用；要是要求三者互不相同，预处理时可以记录(i,j)对，查询时排除k=i或k=j的情况，时间复杂度还是O(N²)，只是多了点判断逻辑。

思路2：优化后的字典树方案（控制时间在O(N²)） #

你提到的字典树思路可以调整实现方式，避免分支导致的时间失控：

• 先把所有数组元素的二进制位（从高位到低位）插入字典树，这一步是O(N*L)，其中L是数值的二进制位数（常数，比如32），所以等价于O(N)。
• 然后对每个x_k，遍历数组里的每个x_i，在字典树里查询是否存在x_j满足x_i ⊕ x_j = x_k（也就是x_j = x_i ⊕ x_k）。每次查询的时间是O(L)，也就是常数时间。
• 这样总操作次数是O(N²)，每次查询是常数，整体时间复杂度就是O(N²)。
• 这种方式避开了你之前双指针的分支问题——不再用双指针在树里找两个数的异或等于x_k，而是把问题转化为“对每个x_i，找x_i⊕x_k是否在数组中”，每个查询都是线性的常数时间，不会出现最坏情况的遍历爆炸。

关于你最初双指针思路的问题 #

你最开始的双指针方案，当x_k当前位为0时需要分支（同时走两个1或两个0节点），最坏情况下会遍历大量节点，时间复杂度可能退化成O(N²*L)甚至更高，达不到作业要求的O(N²)。而上面调整后的字典树方案，把问题拆解成了单次查询，就解决了这个问题。

内容的提问来源于stack exchange，提问作者mafju