LC.P2475[数组中不等三元组的数目]

方法一：暴力

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
    public int unequalTriplets(int[] nums) {
        int n = nums.length, ans = 0;
        for (int i = 0; i < n; ++i) {
            for (int j = i + 1; j < n; ++j) {
                for (int k = j + 1; k < n; ++k) {
                    if (nums[i] != nums[j] && nums[i] != nums[k] && nums[j] != nums[k]) ++ans;
                }
            }
        }
        return ans;
    }
}
  • 时间复杂度：$O(n^3)$
  • 空间复杂度：$O(1)$

方法二：排序

1
2
3
4
5
6
7
8
9
10
11
class Solution {
    public int unequalTriplets(int[] nums) {
        Arrays.sort(nums);
        int n = nums.length, ans = 0;
        for (int i = 0, j = 0; i < n; i = j) {
            while (j < n && nums[j] == nums[i]) ++j;
            ans += i * (j - i) * (n - j);
        }
        return ans;
    }
}
  • 时间复杂度：$O(nlogn)$
  • 空间复杂度：$O(logn)$

方法三：哈希表

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
    public int unequalTriplets(int[] nums) {
        int n = nums.length, ans = 0;
        Map<Integer, Integer> map = new HashMap<>();
        for (int num : nums) {
            map.merge(num, 1, Integer::sum);
        }
        int a = 0;
        for (int b : map.values()) {
            int c = n - a - b;
            ans += a * b * c;
            a += b;
        }
        return ans;
    }
}
  • 时间复杂度：$O(n)$
  • 空间复杂度：$O(n)$