3583. 統計特殊三元組

思路

當一個數字左右邊數字都要比自己大兩倍時，這三個數字就算一組特殊三元組。
所以對一個數字x來說，一共有「左邊2x出現的次數」乘上「右邊2x出現的次數」這麼多個特殊三元組。
由於數字的範圍是 $0 \leq nums[i] \leq 10^5$，用數組紀錄即可。

程式碼

哈希表

class Solution {
public:
    int specialTriplets(vector<int>& nums) {
        const int MOD = 1e9+7;
        const int MX = 1e5;
        int n = nums.size();
        int freq[MX + 1]{};
        vector<int> left(n, 0); // 在自己左邊的數字, 有幾個是自己兩倍
        vector<int> right(n, 0); // 在自己右邊的數字, 有幾個是自己的兩倍
        // 計算left陣列
        for(int i = 0; i < n; ++i) {
            if(nums[i] * 2 <= MX) {
                left[i] = freq[nums[i] * 2];
            }
            freq[nums[i]]++;
        }
        memset(freq, 0, sizeof(freq));
        // 計算 right 陣列
        for(int i = n - 1; i >= 0; --i) {
            if(nums[i] * 2 <= MX) {
                right[i] = freq[nums[i] * 2];
            }
            freq[nums[i]]++;
        }
        // 計算答案
        long long res = 0;
        for(int i = 0; i < n; ++i) {
            res += 1LL * left[i] * right[i];
            res %= MOD;
        }
        return res %= MOD;
    }
};

複雜度分析

• 時間複雜度：$O(n)$
• 空間複雜度：$O(n)$