【LeetCode】形成两个异或相等数组的三元组数目 Java 题解
题目描述
给你一个整数数组 arr 。
现需要从数组中取三个下标 i、j 和 k ,其中 (0 <= i < j <= k < arr.length) 。
a 和 b 定义如下:
a = arr[i] ^ arr[i + 1] ^ ... ^ arr[j - 1]b = arr[j] ^ arr[j + 1] ^ ... ^ arr[k]注意:^ 表示 按位异或 操作。
请返回能够令 a == b 成立的三元组 (i, j , k) 的数目。
复制代码
思路
这是一个异或问题,解决异或问题,需要明确异或运算的基本性质。
异或运算的特性如下:
复制代码
代码
根据题意写出的代码,不能 AC
复制代码
使用前缀和优化,可以 AC
复制代码
总结
第一种方法的时间复杂度是 O (n * n * n * n), 空间复杂度是 O(1)
前缀和解法的时间复杂度是 O (n * n * n), 空间复杂度是 O(n)
坚持每日一题,加油!
版权声明: 本文为 InfoQ 作者【HQ数字卡】的原创文章。
原文链接:【http://xie.infoq.cn/article/f7bfc6dcf756d15818438cac9】。文章转载请联系作者。
评论