This article is participating in the “Java Theme Month – Java Brush questions punch card”, see the activity link for details

Link: leetcode-cn.com/problems/co…

Tags: arrays, bitwise operations, mathematics

The title

I give you an integer array arr.

We now need to fetch three subscripts I, j, and k from the array, where (0 <= I < j <= k < arr.length).

A and B are defined as follows:

  • a = arr[i] ^ arr[i + 1] ^ … ^ arr[j – 1]
  • b = arr[j] ^ arr[j + 1] ^ … ^ arr[k]

Note: ^ represents a bitwise xor operation.

Return the number of triples (I, j, k) that make a == b true.

Input: arr = [2,3,1,6,7] output: 4 explanation: the triples that satisfy the task are (0,1,2,2), (0,2,2), (2,3,4) and (2,4,4) input: arr = [1,1,1,1] output: 10 input: arr = [1,1,1,1] Arr = [2,3] output: 0 input: arr = [1,3,5,7,9] output: 3 input: arr = [7,11,12,9,5,2,7,17,22] 8 1 <= arr.length <= 300 1 <= arr[i] <= 10^8Copy the code

Analysis of the

A ^ b = 0, arr[I] ^ arr[I + 1] ^… ^ arr[j – 1] ^ arr[j] ^ arr[j + 1] ^ … ^ arr[k] = 0

So we only need to solve for I and k, and then any number j in the range of (I, k) can form the required (I, j, k).

So the problem is how many pairs of (I, k) there are, and then we can find how many triples (I, j, k) there are. Note that 0 <= I < j <= k < arr.length, j and k may be the same number, so two numbers can also form a triplet.

So we can figure out the xOR of the first n numbers in the arR array, store it in an array, and then when we loop, we can avoid double-counting.

Class Solution {/** * a == b, then a ^ b = 0, arr[I] ^ arr[I + 1] ^... ^ arr[j - 1] ^ arr[j] ^ arr[j + 1] ^ ... ^ arr[k] = 0 * then we only need to solve for I and k, then any number j in the range of (I, k) can form the required (I, j, k) * so we need to solve for how many pairs of (I, k), Public int countTriplets(int[] arr) {len = arr. Length, res = 0; int[] sum = new int[len + 1]; sum[0] = 0; for (int i = 1; i <= len; i++) { sum[i] = (sum[i - 1] ^ arr[i - 1]); Int I = 1; int I = 1; int I = 1; i <= len - 1; i++) { for (int j = i + 1; j <= len; j++) { if ((sum[j] ^ sum[i - 1]) == 0) { res += (j - i); } } } return res; }}Copy the code

Time O(n ^ 2), space O(n)

The e double loop would have been expected to take a long time. I didn’t realize there was a 100% beat rate.