leetcode
leetcode 2151 ~ 2200
数组中不等三元组的数目

数组中不等三元组的数目

难度:

标签:

题目描述

代码结果

运行时间: 23 ms, 内存: 15.9 MB


/*
 * 思路:
 * 1. 使用Java Stream API来处理三重嵌套循环的逻辑。
 * 2. 使用IntStream来生成索引,然后通过条件过滤出满足条件的三元组。
 * 3. 最终使用count()来计算符合条件的三元组数量。
 */

import java.util.stream.IntStream;

public class Solution {
    public long countDistinctTriplets(int[] nums) {
        int n = nums.length;
        return IntStream.range(0, n - 2)
            .boxed()
            .flatMap(i -> IntStream.range(i + 1, n - 1)
                .boxed()
                .flatMap(j -> IntStream.range(j + 1, n)
                    .filter(k -> nums[i] != nums[j] && nums[i] != nums[k] && nums[j] != nums[k])
                    .mapToObj(k -> new int[]{i, j, k})))
            .count();
    }
}

解释

方法:

这个题解的思路是使用哈希表来记录已经看到的元素的出现次数,并同时遍历数组来构建三元组。具体步骤为: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)

代码细节讲解

🦆
在题解中,为什么选择使用哈希表来记录元素的出现次数而不是直接使用数组?
在题解中,选择使用哈希表而不是数组的主要原因是数组的索引范围有限,并且与数据的最大值有关,这可能导致数组非常大,从而浪费空间。而哈希表可以灵活地根据元素值直接存储和检索元素出现的次数,尤其适用于元素值范围广泛或不连续的情况。此外,哈希表在理想情况下提供接近常数时间的数据访问,这对于频繁的查找和更新操作非常高效。
🦆
题解中提到的方法似乎存在对数组中的每对元素遍历,那么这种方法的时间复杂度是多少?是否可以进一步优化?
题解中的方法涉及两层循环,其中外层循环遍历每个元素作为第一个元素,内层循环遍历后续所有元素作为第二个元素,因此基本操作的数量是关于数组长度的平方级别,即时间复杂度为O(n^2)。尽管已经通过哈希表减少了一些不必要的重复计算,但时间复杂度依然较高。进一步优化可能考虑更高效的数据结构或算法,如使用排序和双指针技术来减少必要的比较次数,从而尝试降低时间复杂度。
🦆
题解中的`seen`哈希表记录的是元素第一次出现的位置,这个信息在计算三元组数量时具体是如何使用的?
在题解中,`seen`哈希表记录每个元素第一次出现的位置用于计算可以与当前元素形成有效三元组的前序元素数量。具体来说,对于每个元素`nums[j]`,通过查看`seen`来找到`nums[j]`首次出现的位置,这个位置之前的所有元素都可以与`nums[j]`形成不等的二元组。然后通过计算当前索引`i`与`nums[j]`首次出现位置的差,我们可以得知在当前元素之前有多少个元素可以与之形成不等的三元组。这样,`seen`的使用帮助我们有效地统计了符合条件的三元组数量,避免了对每个可能的三元组进行详细检查。

相关问题