【算法leetcode】1442. 形成两个异或相等数组的三元组数目（rust真是好用）

---

---

1442. 形成两个异或相等数组的三元组数目：

给你一个整数数组 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)
1
2
3
4
5
6
7
8

样例 2：

输入：
	arr = [1,1,1,1,1]
	
输出：
	10
1
2
3
4
5

样例 3：

输入：
	arr = [2,3]
	
输出：
	0
1
2
3
4
5

样例 4：

输入：
	arr = [1,3,5,7,9]
	
输出：
	3
1
2
3
4
5

样例 5：

输入：
	arr = [7,11,12,9,5,2,7,17,22]
	
输出：
	8
1
2
3
4
5

提示：

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

---

分析

• 面对这道算法题目，二当家的陷入了沉思。
• 根据题意和x ^ x = 0，满足条件的i，j，k一定满足一个特点：arr[i] ^ ... ^ arr[k]=0，而这时候j取(i,k]中的任何值都可以满足条件。
• 设s[i] = arr[0] ^ ... ^ arr[i-1]，当s[i]==s[k+1]相等时，展开可得arr[0] ^ ... ^ arr[i-1]==arr[0] ^ ... ^ arr[k]，根据x ^ 0 = x可以推测出arr[i] ^ ... ^ arr[k]=0。
• 对于下标 k，若下标 i=i₁,i₂,⋯ ,i_m时均满足 S_i=S_k+1，根据前面的推论可得答案数为(k−i_1​)+(k−i₂​)+⋯+(k−i_m​)=m⋅k−(i₁​+i_2​+⋯+i_m​)
• 也就是说，当遍历下标 k 时，我们需要知道所有满足 S_i=S_k+1​ 的
  1. 下标 i 的出现次数 m
  2. 下标 i 之和

---

题解

rust

impl Solution {
    pub fn count_triplets(arr: Vec<i32>) -> i32 {
        let mut ans = 0;
        // 前缀和
        let mut s = 0;
        let mut cnt: std::collections::HashMap<i32, i32> = std::collections::HashMap::new();
        let mut total: std::collections::HashMap<i32, i32> = std::collections::HashMap::new();
        arr.iter().enumerate().for_each(|(k, v)| {
            let t = s ^ v;
            if cnt.contains_key(&(t)) {
                ans += cnt[&(t)] * k as i32 - total[&(t)];
            }
            let counter = cnt.entry(s).or_insert(0);
            *counter += 1;
            let counter = total.entry(s).or_insert(0);
            *counter += k as i32;
            s = t;
        });
        return ans;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

---

go

func countTriplets(arr []int) (ans int) {
    // 前缀和
	s := 0
	cnt := map[int]int{}
	total := map[int]int{}
	for k, v := range arr {
		t := s ^ v
		if m, has := cnt[t]; has {
			ans += m*k - total[t]
		}
		cnt[s]++
		total[s] += k
		s = t
	}
	return
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

---

c++

class Solution {
public:
    int countTriplets(vector<int>& arr) {
        int ans = 0;
        // 前缀和
        int s = 0;
        int n = arr.size();
        unordered_map<int, int> cnt, total;
        for (int k = 0; k < n; ++k) {
            int t = s ^ arr[k];
            if (cnt.count(t)) {
                ans += cnt[t] * k - total[t];
            }
            ++cnt[s];
            total[s] += k;
            s = t;
        }
        return ans;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

---

java

class Solution {
    public int countTriplets(int[] arr) {
        int ans = 0;
		// 前缀和
		int s = 0;
		int n = arr.length;
		Map<Integer, Integer> cnt = new HashMap<Integer, Integer>();
		Map<Integer, Integer> total = new HashMap<Integer, Integer>();
		for (int k = 0; k < n; ++k) {
			int t = s ^ arr[k];
			if (cnt.containsKey(t)) {
				ans += cnt.get(t) * k - total.get(t);
			}
			cnt.put(s, cnt.getOrDefault(s, 0) + 1);
			total.put(s, total.getOrDefault(s, 0) + k);
			s = t;
		}
		return ans;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

---

python

class Solution:
    def countTriplets(self, arr: List[int]) -> int:
        ans = 0
        # 前缀和
        s = 0
        cnt, total = Counter(), Counter()

        for k, v in enumerate(arr):
            if (t := s ^ v) in cnt:
                ans += cnt[t] * k - total[t]
            cnt[s] += 1
            total[s] += k
            s = t

        return ans

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

---

原题传送门：https://leetcode.cn/problems/count-triplets-that-can-form-two-arrays-of-equal-xor/

---

非常感谢你阅读本文~
欢迎【点赞】【收藏】【评论】~
放弃不难，但坚持一定很酷~
希望我们大家都能每天进步一点点~
本文由 二当家的白帽子：https://le-yi.blog.csdn.net/ 博客原创~

---