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

解题思路

由于数组长度较小（最大100），我们可以使用暴力解法来解决这个问题。

方法一：三重循环暴力枚举 最直观的方法是使用三重循环遍历所有可能的三元组 (i, j, k)，其中 i < j < k，然后检查 nums[i]、nums[j] 和 nums[k] 是否两两不同。

方法二：哈希表优化（思路扩展） 可以使用哈希表统计每个数字的出现次数，然后对于每种不同的数字组合进行计算。不过由于数据规模较小，暴力解法已经足够高效。

对于这道题，由于约束条件很小（n ≤ 100），推荐使用方法一的三重循环暴力解法，代码简洁且易于理解。

算法步骤：

  1. 使用三重循环遍历所有满足 i < j < k 的索引组合
  2. 检查 nums[i] != nums[j] && nums[i] != nums[k] && nums[j] != nums[k]
  3. 如果满足条件，计数器加1
  4. 返回最终计数结果

代码实现

class Solution {
public:
    int unequalTriplets(vector<int>& nums) {
        int n = nums.size();
        int count = 0;
        
        for (int i = 0; i < n - 2; i++) {
            for (int j = i + 1; j < n - 1; j++) {
                for (int k = j + 1; k < n; k++) {
                    if (nums[i] != nums[j] && nums[i] != nums[k] && nums[j] != nums[k]) {
                        count++;
                    }
                }
            }
        }
        
        return count;
    }
};

class Solution:
    def unequalTriplets(self, nums: List[int]) -> int:
        n = len(nums)
        count = 0
        
        for i in range(n - 2):
            for j in range(i + 1, n - 1):
                for k in range(j + 1, n):
                    if nums[i] != nums[j] and nums[i] != nums[k] and nums[j] != nums[k]:
                        count += 1
        
        return count

public class Solution {
    public int UnequalTriplets(int[] nums) {
        int n = nums.Length;
        int count = 0;
        
        for (int i = 0; i < n - 2; i++) {
            for (int j = i + 1; j < n - 1; j++) {
                for (int k = j + 1; k < n; k++) {
                    if (nums[i] != nums[j] && nums[i] != nums[k] && nums[j] != nums[k]) {
                        count++;
                    }
                }
            }
        }
        
        return count;
    }
}

var unequalTriplets = function(nums) {
    const n = nums.length;
    let count = 0;
    
    for (let i = 0; i < n - 2; i++) {
        for (let j = i + 1; j < n - 1; j++) {
            for (let k = j + 1; k < n; k++) {
                if (nums[i] !== nums[j] && nums[i] !== nums[k] && nums[j] !== nums[k]) {
                    count++;
                }
            }
        }
    }
    
    return count;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度分析
时间复杂度O(n³)
空间复杂度O(1)

说明：

  • 时间复杂度：需要三重循环遍历所有可能的三元组，总共约 C(n,3) = n(n-1)(n-2)/6 个组合
  • 空间复杂度：只使用了常数额外空间

相关题目