1442. Count Triplets That Can Form Two Arrays of Equal XOR

Given an array of integers arr.

We want to select three indices i, j and k where (0 <= i < j <= k < arr.length).

Let's define a and b as follows:

• a = arr[i] ^ arr[i + 1] ^ ... ^ arr[j - 1]
• b = arr[j] ^ arr[j + 1] ^ ... ^ arr[k]

Note that ^ denotes the bitwise-xor operation.

Return the number of triplets (i, j and k) Where a == b.

Example 1:

Input: arr = [2,3,1,6,7]
Output: 4
Explanation: The triplets are (0,1,2), (0,2,2), (2,3,4) and (2,4,4)

Example 2:

Input: arr = [1,1,1,1,1]
Output: 10

Example 3:

Input: arr = [2,3]
Output: 0

Example 4:

Input: arr = [1,3,5,7,9]
Output: 3

Example 5:

Input: arr = [7,11,12,9,5,2,7,17,22]
Output: 8

Constraints:

• 1 <= arr.length <= 300
• 1 <= arr[i] <= 10^8

class Solution {
    public int countTriplets(int[] arr) {
        int le = arr.length;
        int res = 0;
        for(int i = 0; i < le; i++){
            for(int j = i + 1; j < le; j++){
                for(int k = j; k < le; k++){
                    if(helpA(arr, i, j) == helpB(arr, j, k)){
                        res++;
                    }
                }
            }
        }
        // return set.size();
        return res;
    }
    public int helpA(int[] arr, int i, int j){
        int res = 0;
        for(int t = i; t < j; t++) res = (res ^ arr[t]);
        return res;
    }
    public int helpB(int[] arr, int j, int k){
        int res = 0;
        for(int i = j; i <= k; i++){
            res = (res ^ arr[i]);
        }
        return res;
    }
}

先brute force O（n^3）

把所有可能的ijk找到，res++就行，要注意i, j, k的关系

或者另一种方法

既然判断条件是a == b，那就说明

 那就找所有的i和k满足上面，然后res += k-i.

class Solution {
    public int countTriplets(int[] arr) {
        int res = 0;
        
        for(int i = 0; i < arr.length; i++){
            for(int j = i + 1; j < arr.length; j++){
                int t = 0;
                for(int k = i; k <= j; k++){
                    t = (t ^ arr[k]);
                }
                res += (t == 0) ? (j - i) : 0;
            }
        }
        return res;
    }
}

我麻了，原来可以O（n^2）

class Solution {
     public int countTriplets(int[] arr) {
            int ans = 0;
            int length = arr.length;
            for (int i = 0; i < length; i++) {
                int xor = arr[i];
                for (int j = i + 1; j < length; j++) {
                    xor ^= arr[j];
                    if (xor == 0) {
                        ans += (j - i);
                    }
                }
            }
            return ans;
        }
}