Leetcode-1442-形成两个异或相等数组的三元组数目

Leetcode-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) 的数目。

前言

• 用 ⊕ 表示按位异或运算。
  • 定义长度为 n 的数组 arr 的异或前缀和为

• 这是一个关于 S*i 的递推式，根据该递推式我们可以用 O(n)的时间得到数组 arr 的异或前缀和数组。

方法一 ： 二重循环

• 当等于S_i = S_k+1 时候，[i + 1,k] 中的任何一个j都是满足要求的，故枚举下标i 或者 下标k 即可

class Solution {
    public int countTriplets(int[] arr) {
        // 1. 统计前缀和s[i]
        int n = arr.length;
        int[] s = new int[n + 1];
        for(int i = 0; i < n;i++){
            s[i + 1] = s[i] ^ arr[i];
        }
        // 2. 若a = b ，那么 s[i] = s[k + 1], 即[i + 1,k] 中任意的j都是满足条件的
        // 所以二重循环枚举下标i或k
        int ans = 0;
        for(int i = 0;i < n;i++){
            for(int k = i + 1;k < n;k++){
                if(s[i] == s[k + 1]){
                    ans += k - i;
                }
            }
        }
        // 3. 返回结果
        return ans;
    }
}

复杂度分析

• 时间复杂度：O(n^2)，其中 n 是数组 arr 的长度。
• 空间复杂度：O(n)。

方法二 ： 一重循环

• 当遍历下标k的时候，我们需要知道所有满足S_i = S_k+1

  • 下标 i 出现的次数 = m
  • 下标 i 的和

• 这可以借助两个哈希表来做到, 在遍历下标 k 的同时

  • 一个哈希表统计S_k 的出现次数
  • 另外一个统计S_k 的下标之和

class Solution {
    public int countTriplets(int[] arr) {
        int n = arr.length;
        int[] s = new int[n + 1];
        for (int i = 0; i < n; ++i) {
            s[i + 1] = s[i] ^ arr[i];
        }
        Map<Integer, Integer> cnt = new HashMap<Integer, Integer>();
        Map<Integer, Integer> total = new HashMap<Integer, Integer>();
        int ans = 0;
        for (int k = 0; k < n; ++k) {
            if (cnt.containsKey(s[k + 1])) {
                ans += cnt.get(s[k + 1]) * k - total.get(s[k + 1]);
            }
            cnt.put(s[k], cnt.getOrDefault(s[k], 0) + 1);
            total.put(s[k], total.getOrDefault(s[k], 0) + k);
        }
        return ans;
    }
}

• 复杂度分析
  • 时间复杂度：O(n)，其中 n 是数组 arr 的长度。
  • 空间复杂度：O(n)。我们需要使用 O(n) 的空间存储两个哈希表。

打赏