2364 统计坏数对的数目

题目描述#

给你一个下标从 0 开始的整数数组 nums。如果 i < j 且 j - i != nums[j] - nums[i]，那么我们称 (i, j) 是一个坏数对。

请你返回 nums 中坏数对的总数目。

思路#

直接统计坏数对的数量比较困难,可以转换思路:统计好数对的数量,然后用总数对减去好数对即可得到坏数对的数量。

好数对的定义:

如果 i < j 且 j - i == nums[j] - nums[i],则 (i, j) 是一个好数对
化简后得到: nums[j] - j == nums[i] - i

解题步骤:

计算所有数对的总数:n * (n - 1) / 2
遍历数组,对于每个位置 i,计算 nums[i] - i 的值
使用哈希表统计每个 nums[i] - i 值出现的次数
当遇到相同的 nums[i] - i 值时,说明可以组成好数对,累加到好数对的计数中
最终答案 = 总数对数 - 好数对数

时间复杂度: O(n) 空间复杂度: O(n)

代码#

class Solution {
    public long countBadPairs(int[] nums) {
        long all = (long) nums.length * (nums.length - 1) / 2L;
        long good = 0L;
        // 统计nums[i] - i 的出现次数
        Map<Integer, Integer> cnt = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            int cur = nums[i] - i;
            good += (long) cnt.getOrDefault(cur, 0);
            cnt.merge(cur, 1, Integer::sum);
        }
        return all - good;
    }
}