前缀和之异或篇

1310. 子数组异或查询

1371. 每个元音包含偶数次的最长子字符串

今天遇到了两个「前缀和」结合「异或」的题目，感觉很有意思，特意来总结一波！关于前缀和详细介绍可见 前缀和数组

对于「+ -」操作来说，是一对逆运算，比如：n + 3 - 3 = n

而对于「异或」操作来说，自身就是一种逆运算，任何两个相同的数的异或结果为 0，所以有：n ^ 3 ^ 3 = n

至于为什么有这种特性，可以模拟一下「异或」运算的过程就懂了

来看一个样例：[1,2,3,4,5]

• 其中sum(1,5) = 1 + 2 + 3 + 4 + 5 = 15，sum(1,2) = 1 + 2 = 3，sum(3,5) = 3 + 4 + 5 = 12
• 其中XOR(1,5) = 1 ^ 2 ^ 3 ^ 4 ^ 5 = 1，XOR(1,2) = 1 ^ 2 = 3，XOR(3,5) = 3 ^ 4 ^ 5 = 2

所以：sum(1,2) + sum(3,5) = sum(1,5) -> sum(3,5) = sum(1,5) - sum(1,2)

同理：sum(1,2) ^ sum(3,5) = sum(1,5) -> sum(3,5) = sum(1,5) ^ sum(1,2)

有了这样一个简单的推导，下面直接上题目

子数组异或查询

题目详情可见 子数组异或查询

这个题目就是个模版题，直接把「和」换成「异或」即可

xxxxxxxxxx
public int[] xorQueries(int[] arr, int[][] queries) {
    int[] preSum = new int[arr.length + 1];
    for (int i = 1; i < preSum.length; i++) preSum[i] = preSum[i - 1] ^ arr[i - 1];
    int[] ans = new int[queries.length];
    for (int i = 0; i < queries.length; i++) {
        int[] query = queries[i];
        ans[i] = preSum[query[1] + 1] ^ preSum[query[0]];
    }
    return ans;
}

每个元音包含偶数次的最长子字符串

题目详情可见 每个元音包含偶数次的最长子字符串

我们把五个元音字母看作是五个特殊标记

如果一个子数组里面包含偶数个相同的元音字母，那么这个子数组中所有元音字母的异或结果肯定是 0，因为相同的元素异或为 0。例：'a' ^ 'a' = 0

所以我们只计算含有元音字母的前缀和，非元音字母的位置直接继承前一个结果，具体实现可见代码

xxxxxxxxxx
public int findTheLongestSubstring(String s) {
    List<Character> vowel = Arrays.asList('a', 'e', 'i', 'o', 'u');
    int[] preSum = new int[s.length() + 1];
    for (int i = 1; i < preSum.length; i++) {
        if (vowel.contains(s.charAt(i - 1))) {
            // 如果是元音，就做「异或」操作
            preSum[i] = preSum[i - 1] ^ (int) s.charAt(i - 1);
            // 如果不是元音，直接继承前一个结果
        } else preSum[i] = preSum[i - 1];
    }
    int ans = 0;
    // 结尾从最后一个元素开始搜索 [......i]
    for (int i = s.length() - 1; i >= 0; i--) {
        // 开头从第一个元素开始搜索 [j......]
        // 注意：一定要 j <= i，因为存在 "d" 这样的情况
        for (int j = 0; j <= i; j++) {
            // 如果找到含有偶数个元音的子数组，直接开始上一个元素结尾的搜索
            // 以 i 为结尾的子数组不可能有更长满足条件的情况
            if ((preSum[i + 1] ^ preSum[j]) == 0) {
                ans = Math.max(ans, i - j + 1);
                break;
            }
        }
    }
    return ans;
}