前缀和之等价条件

2364. 统计坏数对的数目

4507. 子数组异或和

本篇文章来总结一下前缀和的变体，其实就是一丢丢的小技巧！！

统计坏数对的数目

题目详情可见 统计坏数对的数目

这是某一次周赛的一道题目，虽然题目不难，但之所以在这里单独拿出来，是为了引出一个小技巧！！

这个题目的关键条件：i < j 且 j - i != nums[j] - nums[i]

如果第一眼没反应过来，估计直接就双重循环了

但是如果稍微把条件改变一波：i < j且nums[i] - i != nums[j] - j，然后把nums[i] - i看作一个整体，借助HashMap，直接一重循环就可以了

下面直接给出代码：

public long countBadPairs(int[] nums) {
    long ans = 0;
    Map<Integer, Integer> map = new HashMap<>();
    for (int i = 0; i < nums.length; i++) {
        int target = nums[i] - i;
        int cnt = map.getOrDefault(target, 0);
        map.put(target, cnt + 1);
        // cnt 是相等的数量，i - cnt 是不等的数量
        ans += i - cnt;
    }
    return ans;
}

虽然这个题目没有用到前缀和，但是确为我们揭示了一个小技巧：利用交换律，使之变成等价条件，利于求解

子数组异或和

题目详情可见 子数组异或和

关于「前缀和数组」的详细介绍可见 前缀和数组、关于「前缀和之异或篇」的详细介绍可见 前缀和之异或篇，建议先看完这两篇文章，否则可能会存在不好理解的地方！！

这个题目的关键条件：sum[i] ^ sum[i - m] = sum[i - m] ^ sum[i - 2m]

同样的，如果第一眼没反应过来，估计直接就双重循环，然后超时！！

但是如果两边同时异或一个sum[i - m]，那么条件就变成了sum[i] = sum[i - 2m]，然后再借助HashMap即可！

这里还有另外一个条件：连续子数组的长度为偶数。怎么才能保证在HashMap中找到的结果满足该条件呢？

如果i为偶数，那么i - 2m为偶数；如果i为奇数，那么i - 2m为奇数，所以只需要用两个HashMap分别存奇偶数即可！

下面直接给出代码：

public long xorSum(int[] nums, int n) {
    long ans = 0;
    // map1 存放奇数；map2 存放偶数
    Map<Integer, Integer> map1 = new HashMap<>();
    Map<Integer, Integer> map2 = new HashMap<>();
    int[] preSum = new int[n + 1];
    for (int i = 1; i <= n; i++) preSum[i] = preSum[i - 1] ^ nums[i - 1];
    map2.put(0, 1);
    for (int i = 1; i <= n; i++) {
        if (i % 2 == 0) {
            int cnt = map2.getOrDefault(preSum[i], 0);
            ans += cnt;
            map2.put(preSum[i], cnt + 1);
        } else {
            int cnt = map1.getOrDefault(preSum[i], 0);
            ans += cnt;
            map1.put(preSum[i], cnt + 1);
        }
    }
    return ans;
}