解法

思路和算法

由于特殊三元组的定义为左边元素值与右边元素值都等于中间元素值的两倍，因此可以遍历中间元素下标并计算每个中间元素下标对应的特殊三元组的数目。

数组 $\textit{nums}$ 的长度是 $n$。对于 $1 \le i < n - 1$ 的每个下标 $i$，如果在下标 $i$ 的左边有 $x$ 个元素 $\textit{nums}[i] \times 2$ 且下标 $i$ 的右边有 $y$ 个元素 $\textit{nums}[i] \times 2$，则以下标 $i$ 作为中间下标的特殊三元组的数目是 $x \times y$。

使用哈希表 $\textit{leftCounts}$ 和 $\textit{rightCounts}$ 分别记录从左到右遍历数组 $\textit{nums}$ 和从右到左遍历数组 $\textit{nums}$ 的过程中的每个元素的出现次数，创建长度为 $n$ 的数组 $\textit{leftSpecial}$ 和 $\textit{rightSpecial}$，对于 $0 \le i < n$ 的每个下标 $i$，$\textit{leftSpecial}[i]$ 表示下标 $i$ 左边的元素值 $\textit{nums}[i] \times 2$ 的个数，$\textit{rightSpecial}[i]$ 表示下标 $i$ 右边的元素值 $\textit{nums}[i] \times 2$ 的个数。根据如下操作计算相应的值。

1. 从左到右遍历数组 $\textit{nums}$。对于遍历到的每个下标 $i$，从哈希表 $\textit{leftCounts}$ 中得到元素 $\textit{nums}[i] \times 2$ 的出现次数填入 $\textit{leftSpecial}[i]$，然后在哈希表 $\textit{leftCounts}$ 中将元素 $\textit{nums}[i]$ 的出现次数增加 $1$。

2. 从右到左遍历数组 $\textit{nums}$。对于遍历到的每个下标 $i$，从哈希表 $\textit{rightCounts}$ 中得到元素 $\textit{nums}[i] \times 2$ 的出现次数填入 $\textit{rightSpecial}[i]$，然后在哈希表 $\textit{rightCounts}$ 中将元素 $\textit{nums}[i]$ 的出现次数增加 $1$。

上述操作中，应首先计算 $\textit{leftSpecial}[i]$ 和 $\textit{rightSpecial}[i]$，然后在哈希表 $\textit{leftCounts}$ 和 $\textit{rightCounts}$ 中更新 $\textit{nums}[i]$ 的出现次数。理由如下：计算 $\textit{leftSpecial}[i]$ 和 $\textit{rightSpecial}[i]$ 时，下标 $i$ 作为特殊三元组的中间下标，因此哈希表 $\textit{leftCounts}$ 和 $\textit{rightCounts}$ 应分别只能包含下标范围 $[0, i - 1]$ 和 $[i + 1, n - 1]$ 中的所有元素的出现次数。如果计算 $\textit{leftSpecial}[i]$ 和 $\textit{rightSpecial}[i]$ 与更新哈希表 $\textit{leftCounts}$ 和 $\textit{rightCounts}$ 的顺序颠倒，则当 $\textit{nums}[i] = 0$ 时会导致错误地计算下标重合的三元组。

由于特殊三元组的中间下标不可能是 $0$ 或 $n - 1$，因此只需要考虑 $1 \le i < n - 1$ 的每个下标 $i$ 作为中间下标的特殊三元组的数目。计算数组 $\textit{leftSpecial}$ 和 $\textit{rightSpecial}$ 之后，从左到右遍历 $1 \le i < n - 1$ 的每个下标 $i$，以下标 $i$ 作为中间下标的特殊三元组的数目是 $\textit{leftSpecial}[i] \times \textit{rightSpecial}[i]$，将该数目加到答案。遍历结束之后，即可得到数组 $\textit{nums}$ 中特殊三元组的总数。

代码

###Java

class Solution {
    static final int MODULO = 1000000007;

    public int specialTriplets(int[] nums) {
        Map<Integer, Integer> leftCounts = new HashMap<Integer, Integer>();
        Map<Integer, Integer> rightCounts = new HashMap<Integer, Integer>();
        int n = nums.length;
        int[] leftSpecial = new int[n];
        int[] rightSpecial = new int[n];
        for (int i = 0; i < n; i++) {
            leftSpecial[i] = leftCounts.getOrDefault(nums[i] * 2, 0);
            leftCounts.put(nums[i], leftCounts.getOrDefault(nums[i], 0) + 1);
        }
        for (int i = n - 1; i >= 0; i--) {
            rightSpecial[i] = rightCounts.getOrDefault(nums[i] * 2, 0);
            rightCounts.put(nums[i], rightCounts.getOrDefault(nums[i], 0) + 1);
        }
        int specialCount = 0;
        for (int i = 1; i < n - 1; i++) {
            int currSpecialCount = (int) ((long) leftSpecial[i] * rightSpecial[i] % MODULO);
            specialCount = (specialCount + currSpecialCount) % MODULO;
        }
        return specialCount;
    }
}

###C#

public class Solution {
    const int MODULO = 1000000007;

    public int SpecialTriplets(int[] nums) {
        IDictionary<int, int> leftCounts = new Dictionary<int, int>();
        IDictionary<int, int> rightCounts = new Dictionary<int, int>();
        int n = nums.Length;
        int[] leftSpecial = new int[n];
        int[] rightSpecial = new int[n];
        for (int i = 0; i < n; i++) {
            leftSpecial[i] = leftCounts.ContainsKey(nums[i] * 2) ? leftCounts[nums[i] * 2] : 0;
            leftCounts.TryAdd(nums[i], 0);
            leftCounts[nums[i]]++;
        }
        for (int i = n - 1; i >= 0; i--) {
            rightSpecial[i] = rightCounts.ContainsKey(nums[i] * 2) ? rightCounts[nums[i] * 2] : 0;
            rightCounts.TryAdd(nums[i], 0);
            rightCounts[nums[i]]++;
        }
        int specialCount = 0;
        for (int i = 1; i < n - 1; i++) {
            int currSpecialCount = (int) ((long) leftSpecial[i] * rightSpecial[i] % MODULO);
            specialCount = (specialCount + currSpecialCount) % MODULO;
        }
        return specialCount;
    }
}

复杂度分析

• 时间复杂度：$O(n)$，其中 $n$ 是数组 $\textit{nums}$ 的长度。需要遍历数组常数次，遍历过程中对于每个元素的操作时间都是 $O(1)$。

• 空间复杂度：$O(n)$，其中 $n$ 是数组 $\textit{nums}$ 的长度。哈希表 $\textit{leftCounts}$ 和 $\textit{rightCounts}$ 以及数组 $\textit{leftSpecial}$ 和 $\textit{rightSpecial}$ 的空间是 $O(n)$。