LeetCode 题解工作台
统计特殊三元组
给你一个整数数组 nums 。 特殊三元组 定义为满足以下条件的下标三元组 (i, j, k) ： 0 ，其中 n = nums.length nums[i] == nums[j] * 2 nums[k] == nums[j] * 2 返回数组中 特殊三元组 的总数。 由于答案可能非常大，请返回结果…
3
题型
6
代码语言
3
相关题
当前训练重点
中等 · 数组·哈希·扫描
答案摘要
我们可以枚举中间数字 ，用两个哈希表 和 分别记录 左侧和右侧的数字出现次数。 我们首先将所有数字加入 中，然后从左到右遍历每个数字 ，在遍历过程中：
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 数组·哈希·扫描 题型思路
题目描述
给你一个整数数组 nums。
特殊三元组 定义为满足以下条件的下标三元组 (i, j, k)：
0 <= i < j < k < n，其中n = nums.lengthnums[i] == nums[j] * 2nums[k] == nums[j] * 2
返回数组中 特殊三元组 的总数。
由于答案可能非常大，请返回结果对 109 + 7 取余数后的值。
示例 1：
输入： nums = [6,3,6]
输出： 1
解释：
唯一的特殊三元组是 (i, j, k) = (0, 1, 2)，其中：
nums[0] = 6,nums[1] = 3,nums[2] = 6nums[0] = nums[1] * 2 = 3 * 2 = 6nums[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] = 0nums[0] = nums[2] * 2 = 0 * 2 = 0nums[3] = nums[2] * 2 = 0 * 2 = 0
示例 3：
输入： nums = [8,4,2,8,4]
输出： 2
解释：
共有两个特殊三元组：
(i, j, k) = (0, 1, 3)nums[0] = 8,nums[1] = 4,nums[3] = 8nums[0] = nums[1] * 2 = 4 * 2 = 8nums[3] = nums[1] * 2 = 4 * 2 = 8
(i, j, k) = (1, 2, 4)nums[1] = 4,nums[2] = 2,nums[4] = 4nums[1] = nums[2] * 2 = 2 * 2 = 4nums[4] = nums[2] * 2 = 2 * 2 = 4
提示：
3 <= n == nums.length <= 1050 <= nums[i] <= 105
解题思路
方法一：枚举中间数字 + 哈希表
我们可以枚举中间数字 ，用两个哈希表 和 分别记录 左侧和右侧的数字出现次数。
我们首先将所有数字加入 中，然后从左到右遍历每个数字 ，在遍历过程中：
- 将 从 中移除。
- 计算 左侧的数字 的出现次数，记为 。
- 计算 右侧的数字 的出现次数，记为 。
- 将 和 相乘，得到以 为中间数字的特殊三元组数量，并将结果累加到答案中。
- 将 加入 中。
最后返回答案。
时间复杂度为 ，空间复杂度为 ，其中 是数组 的长度。
class Solution:
def specialTriplets(self, nums: List[int]) -> int:
left = Counter()
right = Counter(nums)
ans = 0
mod = 10**9 + 7
for x in nums:
right[x] -= 1
ans = (ans + left[x * 2] * right[x * 2] % mod) % mod
left[x] += 1
return ans
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | complexity is O(n) with hash maps since each index is processed once. Space complexity is O(U) where U is the number of unique values in nums, as both freqPrev and freqNext store counts. |
| 空间 | Depends on the final approach |
面试官常问的追问
外企场景- question_mark
Expect you to notice that nested loops will be too slow for large n and suggest a counting map.
- question_mark
Look for the use of separate maps for previous and next frequencies, hinting at array scanning plus hash lookup.
- question_mark
Be ready to explain how you handle indices and avoid double-counting triplets.
常见陷阱
外企场景- error
Incorrectly updating freqPrev or freqNext leading to wrong counts.
- error
Assuming nums[i] != nums[j] automatically implies nums[j] != nums[k], which may overcount.
- error
Forgetting to initialize freqNext properly before scanning the array.
进阶变体
外企场景- arrow_right_alt
Count triplets where nums[i] + nums[j] == nums[k] using similar frequency maps.
- arrow_right_alt
Find quadruplets with a similar condition, extending the hash lookup to two levels.
- arrow_right_alt
Restrict triplets to contiguous subarrays, requiring sliding window plus frequency map.