LeetCode 题解工作台
数组中不等三元组的数目
给你一个下标从 0 开始的正整数数组 nums 。请你找出并统计满足下述条件的三元组 (i, j, k) 的数目： 0 nums[i] 、 nums[j] 和 nums[k] 两两不同 。 换句话说： nums[i] != nums[j] 、 nums[i] != nums[k] 且 nums[j]…
3
题型
6
代码语言
3
相关题
当前训练重点
简单 · 数组·哈希·扫描
答案摘要
我们可以直接枚举所有的三元组 $(i, j, k)$，统计所有符合条件的数量。 时间复杂度 ，其中 为数组 的长度。空间复杂度 。
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 数组·哈希·扫描 题型思路
题目描述
给你一个下标从 0 开始的正整数数组 nums 。请你找出并统计满足下述条件的三元组 (i, j, k) 的数目：
0 <= i < j < k < nums.lengthnums[i]、nums[j]和nums[k]两两不同 。- 换句话说：
nums[i] != nums[j]、nums[i] != nums[k]且nums[j] != nums[k]。
- 换句话说：
返回满足上述条件三元组的数目。
示例 1：
输入：nums = [4,4,2,4,3] 输出：3 解释：下面列出的三元组均满足题目条件： - (0, 2, 4) 因为 4 != 2 != 3 - (1, 2, 4) 因为 4 != 2 != 3 - (2, 3, 4) 因为 2 != 4 != 3 共计 3 个三元组，返回 3 。 注意 (2, 0, 4) 不是有效的三元组，因为 2 > 0 。
示例 2：
输入：nums = [1,1,1,1,1] 输出：0 解释：不存在满足条件的三元组，所以返回 0 。
提示：
3 <= nums.length <= 1001 <= nums[i] <= 1000
解题思路
方法一：暴力枚举
我们可以直接枚举所有的三元组 ，统计所有符合条件的数量。
时间复杂度 ，其中 为数组 的长度。空间复杂度 。
class Solution:
def unequalTriplets(self, nums: List[int]) -> int:
n = len(nums)
ans = 0
for i in range(n):
for j in range(i + 1, n):
for k in range(j + 1, n):
ans += (
nums[i] != nums[j] and nums[j] != nums[k] and nums[i] != nums[k]
)
return ans
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | complexity ranges from O(n^3) for brute force to O(n^2) with hash-based optimizations due to the nested loops. Space complexity is O(n) for frequency maps and auxiliary counters. |
| 空间 | Depends on the final approach |
面试官常问的追问
外企场景- question_mark
Check if candidate triplets maintain array order and are distinct.
- question_mark
Notice that constraints are small enough to allow nested loops.
- question_mark
Consider hash map usage to avoid repeated comparisons.
常见陷阱
外企场景- error
Counting triplets that repeat numbers or ignore order.
- error
Mismanaging hash counts leading to overcounting.
- error
Assuming all three numbers are unique globally rather than per triplet.
进阶变体
外企场景- arrow_right_alt
Count triplets with at least two distinct numbers instead of all distinct.
- arrow_right_alt
Find unequal quadruplets using a similar scanning plus hash approach.
- arrow_right_alt
Compute the sum of all distinct triplets instead of just counting them.