题目描述

给你一个下标从 0 开始的整数数组 nums 。

三个下标 i ，j 和 k 的 有效值 定义为 ((nums[i] | nums[j]) & nums[k]) 。

一个数组的 xor 美丽值 是数组中所有满足 0 <= i, j, k < n  的三元组 (i, j, k) 的 有效值 的异或结果。

请你返回 nums 的 xor 美丽值。

注意：

val1 | val2 是 val1 和 val2 的按位或。
val1 & val2 是 val1 和 val2 的按位与。

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/find-xor-beauty-of-array
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

样例

示例 1：

输入：nums = [1,4]
输出：5
解释：
三元组和它们对应的有效值如下：
- (0,0,0) 有效值为 ((1 | 1) & 1) = 1
- (0,0,1) 有效值为 ((1 | 1) & 4) = 0
- (0,1,0) 有效值为 ((1 | 4) & 1) = 1
- (0,1,1) 有效值为 ((1 | 4) & 4) = 4
- (1,0,0) 有效值为 ((4 | 1) & 1) = 1
- (1,0,1) 有效值为 ((4 | 1) & 4) = 4
- (1,1,0) 有效值为 ((4 | 4) & 1) = 0
- (1,1,1) 有效值为 ((4 | 4) & 4) = 4
数组的 xor 美丽值为所有有效值的按位异或 1 ^ 0 ^ 1 ^ 4 ^ 1 ^ 4 ^ 0 ^ 4 = 5 。
示例 2：

输入：nums = [15,45,20,2,34,35,5,44,32,30]
输出：34
解释：数组的 xor 美丽值为 34 。

想法

i,j,k 具有高度的对称性，于是对于任意一个三元组可以进行分类讨论再结合 a^a == 0 的小技巧对本题进行优化
1）i!=j时：一定有与之对应的一组(j,i,k)。由于(num[i] | num[j]) & num[k] == (num[j] | num[i]) & num[k]，因此这两个“有效值”的异或为0； 2）i==j且i!=k时（即三元组可表示为(i,i,k)）：一定有与之对应的一组(k,k,i)。由于(num[i] | num[i]) & num[k] == (num[k] | num[k]) & num[i]，因此这两个“有效值”的异或为0； 3）i==j且i==k时，“有效值”(num[i] | num[j]) & num[k] == num[i]。 综上，只需要求num[i] (i = 0,1,2,…,n-1)的异或结果。

C++代码

class Solution {
public:
    int xorBeauty(vector<int>& nums) {
        int res = 0;
        for(auto num : nums)
        {
            res ^= num;
        }
        return res;
    }
};