数组中不等三元组的数目【LC2475】
给你一个下标从 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]。
返回满足上述条件三元组的数目*。*
暴力
- 思路：使用三个指针暴力搜寻合法的位置
- 实现
class Solution { public int unequalTriplets(int[] nums) { int len = nums.length; int res = 0; if (len < 3){ return res; } int i = 0; while (i < len - 2){ int j = i + 1; while (j < len - 1){ if (nums[i] != nums[j]){ int k = j + 1; while (k < len){ if (nums[j] != nums[k] && nums[i] != nums[k]){ res++; } k++; } } j++; } i++; } return res; } }
class Solution { public int unequalTriplets(int[] nums) { Arrays.sort(nums); int l = 0; int ans = 0; int len = nums.length; while (l < len ){ int r = l + 1;// 寻找与nums[l]不相等的第一个数 while (r < len && nums[l] == nums[r]){ r++; } ans += l * (r - l) * ( len - r); l = r; } return ans; } }
哈希表
- 思路：由于三元组中元素的数值的顺序是不重要的，只需要值不相等既可，因此可以直接用哈希表统计num出现的次数，然后遍历哈希表，假设
- 在其之前遍历的元素有a个
- 等于其的元素有b个
- 在其之后遍历的元素有c个
那么，根据组合原理，该元素对结果的贡献为a∗b∗c
实现
class Solution { public int unequalTriplets(int[] nums) { Map<Integer,Integer> map = new HashMap<>(); int ans = 0; int len = nums.length; for (int i = 0; i < len; i++){ map.put(nums[i], map.getOrDefault(nums[i],0) + 1); } int l = 0; int r = len; for (Map.Entry<Integer,Integer> node : map.entrySet()){ int count = node.getValue(); r -= count; ans += l * count * r; l += count; } return ans; } }
