数组中不等三元组的数目

难度: Easy

给你一个下标从 0 开始的正整数数组 nums 。请你找出并统计满足下述条件的三元组 (i, j, k) 的数目：

0 <= i < j < k < nums.length
nums[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 <= 100
1 <= nums[i] <= 1000

Submission

运行时间: 23 ms

内存: 15.9 MB

class Solution:
    def unequalTriplets(self, nums: List[int]) -> int:
        res = 0
        seen = {nums[0]: 1}
        n = len(nums)
        for i in range(1, n - 1):
            cnt=0
            for j in range(i + 1, n):
                if nums[i] == nums[j]: continue
                k = seen[nums[j]] if nums[j] in seen else 0
                res += i - k
                cnt+=1
            if nums[i] in seen:
                res -= seen[nums[i]]*cnt
                seen[nums[i]] += 1
            else:
                seen[nums[i]] = 1
        return res

Explain

这个题解的思路是使用哈希表来记录已经看到的元素的出现次数，并同时遍历数组来构建三元组。具体步骤为：1. 初始化哈希表 `seen` 记录每个元素第一次出现时的位置。2. 从第二个元素开始遍历数组，对于每个元素 `nums[i]`，检查后续的每个元素 `nums[j]`，如果 `nums[i] != nums[j]`，那么尝试构建三元组。3. 对于每个有效的 `j`，计算在 `i` 之前且值等于 `nums[j]` 的元素的个数，这个数量可以通过 `seen` 获取。4. 更新结果 `res`，以及适当的更新 `seen` 哈希表。这个方法试图通过减少重复计算和有效利用哈希表来提高效率，但由于内部的嵌套循环，依然可能存在高的时间复杂度。

时间复杂度: O(n^2)

空间复杂度: O(n)

class Solution:
    def unequalTriplets(self, nums: List[int]) -> int:
        res = 0  # 最终的三元组数量
        seen = {nums[0]: 1}  # 记录元素首次出现的位置
        n = len(nums)  # 数组的长度
        for i in range(1, n - 1):  # 从第二个元素开始遍历
            cnt = 0  # 记录当前元素与后续元素不同的个数
            for j in range(i + 1, n):  # 遍历当前元素后面的所有元素
                if nums[i] == nums[j]: continue  # 如果当前元素与后续元素相同，则跳过
                k = seen[nums[j]] if nums[j] in seen else 0  # 计算之前出现相同元素的次数
                res += i - k  # 根据之前元素的位置更新结果
                cnt += 1  # 更新计数
            if nums[i] in seen:
                res -= seen[nums[i]] * cnt  # 如果当前元素之前出现过，修正重复计数
                seen[nums[i]] += 1  # 更新出现次数
            else:
                seen[nums[i]] = 1  # 如果是首次出现，记录位置
        return res  # 返回结果

Explore

在题解中，选择使用哈希表而不是数组的主要原因是数组的索引范围有限，并且与数据的最大值有关，这可能导致数组非常大，从而浪费空间。而哈希表可以灵活地根据元素值直接存储和检索元素出现的次数，尤其适用于元素值范围广泛或不连续的情况。此外，哈希表在理想情况下提供接近常数时间的数据访问，这对于频繁的查找和更新操作非常高效。

题解中的方法涉及两层循环，其中外层循环遍历每个元素作为第一个元素，内层循环遍历后续所有元素作为第二个元素，因此基本操作的数量是关于数组长度的平方级别，即时间复杂度为O(n^2)。尽管已经通过哈希表减少了一些不必要的重复计算，但时间复杂度依然较高。进一步优化可能考虑更高效的数据结构或算法，如使用排序和双指针技术来减少必要的比较次数，从而尝试降低时间复杂度。

在题解中，`seen`哈希表记录每个元素第一次出现的位置用于计算可以与当前元素形成有效三元组的前序元素数量。具体来说，对于每个元素`nums[j]`，通过查看`seen`来找到`nums[j]`首次出现的位置，这个位置之前的所有元素都可以与`nums[j]`形成不等的二元组。然后通过计算当前索引`i`与`nums[j]`首次出现位置的差，我们可以得知在当前元素之前有多少个元素可以与之形成不等的三元组。这样，`seen`的使用帮助我们有效地统计了符合条件的三元组数量，避免了对每个可能的三元组进行详细检查。