检查数组中是否有3个数字异或等于0

Question

给定 N 个实数数组 x_1, x_2, ..., x_n，检查是否存在 1 <= i,j,k <= n such that x_i ⊕ x_j ⊕ x_k = 0, where ⊕ is XOR operation.

这是大学作业，必须在 O(N^2) 时间复杂度内完成。

我的第一个想法是将所需的方程更改为 x_i ⊕ x_j = x_k。然后对于数组中的每个数字，将其选为 x_k 并尝试找到异或等于它的两个数字。

然后为了解决这个2-XOR问题，我考虑制作数组中数字的二进制表示形式的trie，因此trie中的每个节点都是某个数字的单个位，并且从根到叶的每条路径代表整数。 然后使用两个指针从根开始查看x_k的第一位。如果为 1，则第一个指针需要指向 1 节点，第二个指针需要指向 0 节点。这里的问题是，如果 x_k 的某些位为 0，那么我们的指针可以指向两个 1 节点或两个 0 节点。似乎我需要检查这两个选项，但现在我真的不知道这会如何影响复杂性。看来最坏的情况我们每次都会遍历 trie 中的所有节点，所以我不确定复杂性是多少。

我不关心代码，我只需要一个想法和时间复杂度的近似值。

Answer 1

给定 x_i ⊕ x_j = x_k，您可以使用哈希映射/集合来记住 x_i ⊕ x_j 和 x_k，并在迭代所有数组项组合时检查它们。这不会给你超过 O(n^2) 的复杂性。 x_i ⊕ x_j 和 x_k 也可以存储在涉及二分搜索的排序数组中。您还可以对原始数组进行排序并对其进行二分搜索以查找 x_k。

const arr = [4,5,6,7,8,9,10,11,12,13,14];


const hasXORs = arr => {

  const xors = new Map;
  const nums = new Set;

  for(let i=0;i<arr.length;i++){
    const n=arr[i];
    if(xors.has(n)) return [...xors.get(n), n];
    for(let j=i+1;j<arr.length;j++){
      const n2 = arr[j];
      const xor = n ^ n2;
      if(nums.has(xor)) return [n, n2, xor];
    }
    nums.add(n);
  }
};

console.log(...hasXORs(arr));