点击获取AI摘要

2364. 统计坏数对的数目 M

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

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

示例 1：

输入：nums = [4,1,3,3]
输出：5
解释：数对 (0, 1) 是坏数对，因为 1 - 0 != 1 - 4 。
数对 (0, 2) 是坏数对，因为 2 - 0 != 3 - 4, 2 != -1 。
数对 (0, 3) 是坏数对，因为 3 - 0 != 3 - 4, 3 != -1 。
数对 (1, 2) 是坏数对，因为 2 - 1 != 3 - 1, 1 != 2 。
数对 (2, 3) 是坏数对，因为 3 - 2 != 3 - 3, 1 != 0 。
总共有 5 个坏数对，所以我们返回 5 。

示例 2：

输入：nums = [1,2,3,4,5]
输出：0
解释：没有坏数对。

提示：

  • 1 <= nums.length <= 10510^5
  • 1 <= nums[i] <= 10910^9

问题分析

1.化简判定条件

我们通过数学变换将条件转化为统计差值相等的数对数量，最终用总数减去好的数对得到答案：

对于一对索引 i<ji<j，当且仅当

j−i=nums[j]−nums[i]j - i = \text{nums}[j] - \text{nums}[i]

时，这对 (i,j)(i,j) 不是坏数对；等价于

nums[j]−j=nums[i]−i.\text{nums}[j] - j = \text{nums}[i] - i.

将所有元素映射为“调整值” Ak=nums[k]−kA_k = \text{nums}[k] - k，计算所有元素与索引的差值，统计相同差值出现次数，则“好数对”数目就是所有相同 AA 值之间的组合对数。

2.总对数与好对数

数组长度为 nn 时，总对数为 n(n−1)2\tfrac{n(n-1)}2。

对于每个不同的调整值 vv，若出现次数为 cvc_v，则它内部的好对数为 cv(cv−1)2\tfrac{c_v(c_v-1)}2。

坏数对数 = 总对数 – ∑vcv(cv−1)2\displaystyle\sum_v \tfrac{c_v(c_v-1)}2。

算法思路

  1. 遍历一次数组，使用哈希表统计每个 Ak=nums[k]−kA_k=\text{nums}[k]-k 出现的频次。
  2. 计算总对数 n(n−1)2\tfrac{n(n-1)}2。
  3. 对哈希表中每个频次 cc，累加 c(c−1)2\tfrac{c(c-1)}2 得到“好对数”。
  4. 用总对数减去好对数，得到坏数对数。

时间复杂度

时间复杂度：O(n)O(n)，只需一次遍历加上对哈希表的小量遍历。

空间复杂度：O(n)O(n)，哈希表最坏存储 nn 个不同键。

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution:
    def countBadPairs(self, nums: list[int]) -> int:
        from collections import Counter
        
        n = len(nums)
        # 1. 统计调整值频次
        freq = Counter(nums[i] - i for i in range(n))
        
        # 2. 总对数
        total_pairs = n * (n - 1) // 2
        
        # 3. 累加所有“好对数”
        good_pairs = sum(c * (c - 1) // 2 for c in freq.values())
        
        # 4. 坏数对 = 总对数 - 好对数
        return total_pairs - good_pairs