class Solution {
public:
int unequalTriplets(vector<int>& nums) {
}
};
6241. 数组中不等三元组的数目
给你一个下标从 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原站题解
golang 解法, 执行用时: 4 ms, 内存消耗: 2.2 MB, 提交时间: 2022-11-21 15:11:25
func unequalTriplets(nums []int) (ans int) {
cnt := map[int]int{}
for _, v := range nums {
cnt[v]++
}
a, c := 0, len(nums)
for _, b := range cnt {
c -= b
ans += a * b * c
a += b
}
return
}
golang 解法, 执行用时: 4 ms, 内存消耗: 2 MB, 提交时间: 2022-11-21 15:11:10
func unequalTriplets(nums []int) (ans int) {
sort.Ints(nums)
start, n := 0, len(nums)
for i, x := range nums[:n-1] {
if x != nums[i+1] {
ans += start * (i - start + 1) * (n - 1 - i)
start = i + 1
}
}
return
}
python3 解法, 执行用时: 36 ms, 内存消耗: 14.8 MB, 提交时间: 2022-11-21 15:10:50
class Solution:
def unequalTriplets(self, nums: List[int]) -> int:
ans, a, c = 0, 0, len(nums)
for b in Counter(nums).values():
c -= b
ans += a * b * c
a += b
return ans
python3 解法, 执行用时: 48 ms, 内存消耗: 14.9 MB, 提交时间: 2022-11-21 15:04:07
class Solution:
def unequalTriplets(self, nums: List[int]) -> int:
nums.sort()
ans = start = 0
for i, (x, y) in enumerate(pairwise(nums)):
if x != y:
ans += start * (i - start + 1) * (len(nums) - 1 - i)
start = i + 1
return ans