給你一個整數數組 arr 。
現需要從數組中取三個下標 i、j 和 k ，其中 (0 <= i < j <= k < arr.length) 。
a 和 b 定義如下：
a = arr[i] ^ arr[i + 1] ^ … ^ arr[j - 1]
b = arr[j] ^ arr[j + 1] ^ … ^ arr[k]
注意：^ 表示 按位異或 操作。
請返回能夠令 a == b 成立的三元組 (i, j , k) 的數目。
示例 1：
輸入：arr = [2,3,1,6,7]
輸出：4
解釋：滿足題意的三元組分別是 (0,1,2), (0,2,2), (2,3,4) 以及 (2,4,4)
示例 2：
輸入：arr = [1,1,1,1,1]
輸出：10
示例 3：
輸入：arr = [2,3]
輸出：0
示例 4：
輸入：arr = [1,3,5,7,9]
輸出：3
示例 5：
輸入：arr = [7,11,12,9,5,2,7,17,22]
輸出：8
解題思路
因為題目中
a 和 b 定義如下：
a = arr[i] ^ arr[i + 1] ^ … ^ arr[j - 1]
b = arr[j] ^ arr[j + 1] ^ … ^ arr[k]
前綴異或數組s[j],代表前i個數字的異或結果
- s[j]=arr[0]^…arr[j-1]
- s[i]=arr[0]^…arr[i-1]
- s[k+1]=arr[0]^…arr[k]
- s[i…j]=arr[i]^… arr[j-1]=a=s[i] ^s[j]
- s[j…k+1]=arr[j]^…arr[k]=b=s[j] ^ s[k+1]
要使得a=b，則s[i]^s[j]=s[j] ^s[k+1]，即s[i]=s[k+1]
- 因為i<k+1恒成立，所以我們可以在構造前綴異或數組的同時，用map記錄下前面出現的s[i]，在計算s[k+1]以后，檢查前面出現過的s[i].
- 又因為使得a=b成立的子數組，只需要滿足s[i]=s[k+1]，與j的值無關，所以在i < j <= k的范圍內，所有j的取值均滿足條件。所以滿足s[i]=s[k+1]后，滿足條件的子數組增加為k-i,因為在前面的與s[k+1]相等的s[i]值，不止一個，所以有（k-i1）+(k-i22)…+(k-im)=m*k-(i1+i2…+im)
所以我們只需要用map記錄下s[i]值對應的
- m：s[i]這個值出現的次數
- (i1+i2…+im)：s[i]這個值出現的下標之和
代碼
func countTriplets(arr []int) int {res,pre:=0,0cnt := map[int]int{}sum:=map[int]int{}for k, value := range arr {cur,exis := cnt[pre^value]if exis{res+=cur*k-sum[pre^value]}cnt[pre]++sum[pre]+=kpre^=value}return res
}
