1442.形成两个异或相等数组的三元组数目

链接：1442.形成两个异或相等数组的三元组数目
难度：Medium
标签：位运算、数组、哈希表、数学、前缀和
简介：请返回能够令 a == b 成立的三元组 (i, j , k) 的数目。

题解 1 - typescript

• 编辑时间：2021-05-18
• 执行用时：148ms
• 内存消耗：39.8MB
• 编程语言：typescript
• 解法介绍：前缀和。

function countTriplets(arr: number[]): number {
  const len = arr.length;
  if (len === 1) return 0;
  let ans = 0;
  const prefixSumList: number[] = [ans, ...arr.map(v => (ans ^= v))];
  ans = 0;
  for (let k = 1; k < len; k++) {
    for (let j = 1; j <= k; j++) {
      for (let i = 0; i < j; i++) {
        const a = prefixSumList[j] ^ prefixSumList[i];
        const b = prefixSumList[k + 1] ^ prefixSumList[j];
        if (a === b) ans++;
      }
    }
  }
  return ans;
}

题解 2 - typescript

• 编辑时间：2021-05-18
• 执行用时：100ms
• 内存消耗：40.3MB
• 编程语言：typescript
• 解法介绍：在前后相等的情况下，可取任意 j。

function countTriplets(arr: number[]): number {
  const len = arr.length;
  if (len === 1) return 0;
  let ans = 0;
  const prefixSumList: number[] = [ans, ...arr.map(v => (ans ^= v))];
  ans = 0;
  for (let k = 1; k < len; k++) {
    for (let i = 0; i < k; i++) {
      if (prefixSumList[k + 1] === prefixSumList[i]) ans += k - i;
    }
  }
  return ans;
}