3583.统计特殊三元组

🎯 问题描述

描述：
给你一个整数数组 nums。
如果三元组 (i, j, k) 满足以下条件，我们称之为特殊三元组：

  1. 0 <= i < j < k < n
  2. nums[i] == 2 * nums[j]
  3. nums[k] == 2 * nums[j]

换句话说，中间元素 nums[j] 的两倍必须等于左边元素 nums[i] 和右边元素 nums[k]。
请你返回特殊三元组的数目。由于答案可能很大，请返回它对 109+710^9 + 7 取余的结果。

说明：

  • 这是一个枚举中间点结合**动态计数（滑动窗口）**的问题。

  • 核心策略：固定中间下标 j，我们需要快速知道 j 左侧有多少个 2 * nums[j]，以及 j 右侧有多少个 2 * nums[j]。

  • 优化点：不需要每次都重新遍历左右子数组。随着 j 向右移动，我们只需要将元素从“右侧计数器”移动到“左侧计数器”即可。

  • 示例：

  • 示例 1：

1
2
3
4
5
6
7
8
9
10
11
输入：nums = [2, 1, 4, 1, 2]
输出：4
解释：
- 目标关系：左右元素是中间元素的两倍。
- j=1 (nums[1]=1): 目标值 target = 2。
  - 左侧 [2]: 有1个2。右侧 [4, 1, 2]: 有1个2。
  - 贡献：1 * 1 = 1。
- j=3 (nums[3]=1): 目标值 target = 2。
  - 左侧 [2, 1, 4]: 有1个2。右侧 [2]: 有1个2。
  - 贡献：1 * 1 = 1。
- (注：具体数值取决于数组内容，此处仅为逻辑演示)

💻 解题思路

思路1：动态维护前后缀计数

核心逻辑

  1. 初始化计数器：
    • count2（右侧计数器）：初始化为整个数组的频次统计。
    • count1（左侧计数器）：初始化为空（或者只包含第一个元素，视循环起点而定）。
  2. 枚举中间点 j：
    • 遍历 j 从 1 到 n-2。
    • 关键操作：在检查 j 之前，nums[j] 实际上还属于“右侧”区域（或者刚要从右侧移除）。我们需要先将 nums[j] 从 count2 中减去，因为它即将成为中间点，不能再作为右边的 k。
  3. 计算贡献：
    • 目标值 target = nums[j] * 2。
    • 检查 count1[target]（左侧有多少个目标值）和 count2[target]（右侧有多少个目标值）。
    • 累加 count1[target] * count2[target]。
  4. 更新左侧计数器：
    • 处理完 j 后，将 nums[j] 加入 count1，因为它对于下一个中间点 j+1 来说，就变成了左侧元素。

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
class Solution:
    def specialTriplets(self, nums: List[int]) -> int:
        mod = 10**9 + 7
        n = len(nums)
        ans = 0
        
        # 1. 初始化右侧计数器（包含所有元素）
        count2 = Counter(nums)
        
        # 2. 初始化左侧计数器
        # 初始时左侧为空，但为了配合循环逻辑，我们先处理第一个元素
        # 实际上，j从1开始，所以nums[0]在循环开始前就应该在左侧
        count1 = defaultdict(int)
        count1[nums[0]] = 1
        
        # 将nums[0]从右侧移除，因为它已经在左侧了
        count2[nums[0]] -= 1
        
        # 3. 枚举中间点 j (从 1 到 n-2)
        for j in range(1, n - 1):
            # 4. 将当前元素 nums[j] 从右侧计数器移除
            # 因为 j 变成了中间点，不再是右侧的候选 k
            count2[nums[j]] -= 1
            
            # 5. 计算当前 j 的贡献
            target = nums[j] * 2
            ans += count1[target] * count2[target]
            
            # 6. 将当前元素 nums[j] 加入左侧计数器
            # 对于下一个 j+1 来说，当前的 nums[j] 就是左侧的候选 i
            count1[nums[j]] += 1
            
        return ans % mod

📊 性能分析

  • 时间复杂度：O(N)O(N)
    • 初始化 Counter 需要 O(N)O(N)。
    • 遍历数组一次，每次循环内的哈希表操作（加减、查找）都是 O(1)O(1)。
    • 总时间复杂度为 O(N)O(N)。
  • 空间复杂度：O(N)O(N)
    • 两个哈希表 count1 和 count2 最多存储 NN 个键值对。

思考

  1. 为什么这是 O(N)O(N) 而不是 O(N2)O(N^2)？

    • 上一题的解法在每次循环中都会重新切片并统计 Counter，这导致了 O(N2)O(N^2)。
    • 本题通过增量更新，每次只做常数次哈希表操作，避免了重复遍历子数组。

  2. 元素归属的流转：

    • 每个元素 nums[x] 的状态流转如下：
      • 初始：在 count2 中。
      • 当 j 扫过它之前：作为右侧元素（候选 k）。
      • 当 j == x：从 count2 移除，作为中间元素（j）。
      • 当 j > x：加入 count1，作为左侧元素（候选 i）。

  3. 边界处理：

    • 代码在循环前手动处理了 nums[0]，将其放入 count1 并从 count2 移除。这是为了保证循环从 j=1 开始时，左侧区域 [0, 0] 是正确的。
    • 循环结束时 j = n-2，此时 nums[n-1] 还在 count2 中，作为右侧元素被正确统计。