Medium

题目描述

给你一个整数数组 nums。

特殊三元组定义为满足以下条件的三元组索引 (i, j, k)：

  • 0 <= i < j < k < n，其中 n = nums.length
  • nums[i] == nums[j] * 2
  • nums[k] == nums[j] * 2

返回数组中特殊三元组的总数。

由于答案可能很大，请返回对 10^9 + 7 取模的结果。

示例 1：

输入：nums = [6,3,6]
输出：1
解释：
唯一的特殊三元组是 (i, j, k) = (0, 1, 2)，其中：
- nums[0] = 6, nums[1] = 3, nums[2] = 6
- nums[0] = nums[1] * 2 = 3 * 2 = 6
- nums[2] = nums[1] * 2 = 3 * 2 = 6

示例 2：

输入：nums = [0,1,0,0]
输出：1
解释：
唯一的特殊三元组是 (i, j, k) = (0, 2, 3)，其中：
- nums[0] = 0, nums[2] = 0, nums[3] = 0
- nums[0] = nums[2] * 2 = 0 * 2 = 0
- nums[3] = nums[2] * 2 = 0 * 2 = 0

示例 3：

输入：nums = [8,4,2,8,4]
输出：2
解释：
恰好有两个特殊三元组：
- (i, j, k) = (0, 1, 3)
- (i, j, k) = (1, 2, 4)

提示：

  • 3 <= n == nums.length <= 10^5
  • 0 <= nums[i] <= 10^5

解题思路

这道题要求找到满足条件的三元组 (i, j, k)，其中 nums[i] == nums[j] * 2 且 nums[k] == nums[j] * 2。

核心思路： 对于每个位置 j，我们需要统计在它之前有多少个元素等于 nums[j] * 2，以及在它之后有多少个元素等于 nums[j] * 2。这两个数量的乘积就是以位置 j 为中心的特殊三元组数量。

优化策略： 使用频率数组来动态维护前缀和后缀的元素频率：

  1. 初始化时，将所有元素的频率存储在 freqNext 中
  2. 遍历数组，对于每个位置 j：
    • 从 freqNext 中移除当前元素
    • 计算当前位置作为中间元素时的贡献：freqPrev[nums[j] * 2] * freqNext[nums[j] * 2]
    • 将当前元素添加到 freqPrev 中

这种方法避免了三重循环，时间复杂度降为 O(n)，是最优解法。

需要注意的是，当 nums[j] * 2 超出数组范围时要特别处理，以及结果需要对 10^9 + 7 取模。

代码实现

class Solution {
public:
    int specialTriplets(vector<int>& nums) {
        const int MOD = 1e9 + 7;
        const int MAX_VAL = 1e5;
        int n = nums.size();
        
        vector<int> freqPrev(MAX_VAL + 1, 0);
        vector<int> freqNext(MAX_VAL + 1, 0);
        
        // 初始化freqNext
        for (int num : nums) {
            freqNext[num]++;
        }
        
        long long result = 0;
        
        for (int j = 0; j < n; j++) {
            freqNext[nums[j]]--;
            
            // 检查nums[j] * 2是否在有效范围内
            if (nums[j] <= MAX_VAL / 2) {
                int target = nums[j] * 2;
                long long count = (long long)freqPrev[target] * freqNext[target];
                result = (result + count) % MOD;
            }
            
            freqPrev[nums[j]]++;
        }
        
        return result;
    }
};

class Solution:
    def specialTriplets(self, nums: List[int]) -> int:
        MOD = 10**9 + 7
        MAX_VAL = 10**5
        n = len(nums)
        
        freq_prev = [0] * (MAX_VAL + 1)
        freq_next = [0] * (MAX_VAL + 1)
        
        # 初始化freq_next
        for num in nums:
            freq_next[num] += 1
        
        result = 0
        
        for j in range(n):
            freq_next[nums[j]] -= 1
            
            # 检查nums[j] * 2是否在有效范围内
            if nums[j] <= MAX_VAL // 2:
                target = nums[j] * 2
                count = freq_prev[target] * freq_next[target]
                result = (result + count) % MOD
            
            freq_prev[nums[j]] += 1
        
        return result

public class Solution {
    public int SpecialTriplets(int[] nums) {
        const int MOD = 1000000007;
        const int MAX_VAL = 100000;
        int n = nums.Length;
        
        int[] freqPrev = new int[MAX_VAL + 1];
        int[] freqNext = new int[MAX_VAL + 1];
        
        // 初始化freqNext
        foreach (int num in nums) {
            freqNext[num]++;
        }
        
        long result = 0;
        
        for (int j = 0; j < n; j++) {
            freqNext[nums[j]]--;
            
            // 检查nums[j] * 2是否在有效范围内
            if (nums[j] <= MAX_VAL / 2) {
                int target = nums[j] * 2;
                long count = (long)freqPrev[target] * freqNext[target];
                result = (result + count) % MOD;
            }
            
            freqPrev[nums[j]]++;
        }
        
        return (int)result;
    }
}

var specialTriplets = function(nums) {
    const MOD = 1e9 + 7;
    const MAX_VAL = 1e5;
    const n = nums.length;
    
    const freqPrev = new Array(MAX_VAL + 1).fill(0);
    const freqNext = new Array(MAX_VAL + 1).fill(0);
    
    // 初始化freqNext
    for (const num of nums) {
        freqNext[num]++;
    }
    
    let result = 0;
    
    for (let j = 0; j < n; j++) {
        freqNext[nums[j]]--;
        
        // 检查nums[j] * 2是否在有效范围内
        if (nums[j] <= Math.floor(MAX_VAL / 2)) {
            const target = nums[j] * 2;
            const count = freqPrev[target] * freqNext[target];
            result = (result + count) % MOD;
        }
        
        freqPrev[nums[j]]++;
    }
    
    return result;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型分析
时间复杂度O(n)，其中 n 是数组长度。只需要遍历数组一次，每次操作都是 O(1)
空间复杂度O(MAX_VAL)，使用了两个大小为 MAX_VAL + 1 的频率数组，其中 MAX_VAL = 10^5