2475. Number of Unequal Triplets in Array

Iterate

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
    public int unequalTriplets(int[] nums) {
        Arrays.sort(nums);

        int count = 0;
        for (int i = 0; i < nums.length - 2; i++) {
            for (int j = i + 1; j < nums.length - 1; j++) {
                if (nums[j] == nums[i]) {
                    continue;
                }
                
                for (int k = j + 1; k < nums.length; k++) {
                    if (nums[k] == nums[j]) {
                        continue;
                    }
                    count += nums.length - k;
                    break;
                }
            }
        }
        return count;
    }
}

Iterate

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
    public int unequalTriplets(int[] nums) {
        Arrays.sort(nums);

        int count = 0;
        // 使用索引 j 枚举中间数 b
        for (int j = 0, k = 0; j < nums.length - 1; j = k) {
            while (k < nums.length && nums[k] == nums[j]) {
                k++;
            }
            // now: nums[k] != nums[j]
            // 中间数字 b 的索引范围：[j, k - 1]
            int countA = j, countB = k - 1 - j + 1, countC = nums.length - countA - countB;
            count += countA * countB * countC;
        }
        return count;
    }
}

Math

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
    public int unequalTriplets(int[] nums) {
        Map<Integer, Integer> valueToCountMap = new HashMap<>();
        for (int num : nums) {
            valueToCountMap.put(num, valueToCountMap.getOrDefault(num, 0) + 1);
        }
        
        int totalCount = 0;
        int countA = 0;
        for (int b : valueToCountMap.keySet()) {
            int countB = valueToCountMap.get(b);
            int countC = nums.length - countA - countB;
            totalCount += countA * countB * countC;
            countA += countB;
        }
        return totalCount;
    }
}

References

2475. Number of Unequal Triplets in Array