统计坏数对的数目

难度: Medium

给你一个下标从 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 <= 10⁵
1 <= nums[i] <= 10⁹

Submission

运行时间: 84 ms

内存: 36.6 MB

class Solution:
    def countBadPairs(self, nums: List[int]) -> int:
        n = len(nums)
        arr = [x - i for i, x in enumerate(nums)]
        cnt = Counter(arr)
        ttl = n * (n - 1) // 2
        for v in cnt.values():
            if v >= 2:
                ttl -= v * (v - 1) // 2
        return ttl

Explain

此解法通过巧妙的转换将问题简化。首先，定义好数对条件为 j - i = nums[j] - nums[i]，这可以转化为 nums[j] - j = nums[i] - i。因此，我们可以通过一个数组 arr 存储每个索引位置上的 nums[i] - i 的值，并使用计数器统计各个值的出现次数。所有可能的数对数量为 n * (n - 1) / 2，其中 n 是数组的长度。然后，对于计数器中每个值的出现次数 v，如果 v >= 2，则计算出所有这些索引可以形成的好数对个数 v * (v - 1) / 2 并从总数对中减去，以得到坏数对的总数。

时间复杂度: O(n)

空间复杂度: O(n)

# 定义解题类
class Solution:
    def countBadPairs(self, nums: List[int]) -> int:
        n = len(nums)  # 数组长度
        arr = [x - i for i, x in enumerate(nums)]  # 计算每个位置的 nums[i] - i
        cnt = Counter(arr)  # 统计每个值的出现次数
        ttl = n * (n - 1) // 2  # 计算总的数对数量
        for v in cnt.values():  # 遍历每个值的计数
            if v >= 2:  # 如果某个值出现超过1次
                ttl -= v * (v - 1) // 2  # 减去这些索引形成的好数对数量
        return ttl  # 返回坏数对总数

Explore

原始问题中，好数对的定义是两个索引 i 和 j（i < j）满足 j - i = nums[j] - nums[i]。将此等式重写为 nums[j] - j = nums[i] - i。这意味着，只要两个不同的索引 i 和 j 对应的 nums[i] - i 与 nums[j] - j 相等，他们就可以形成一个好数对。因此，通过计算每个索引的 nums[i] - i 值，并统计每个这样的值出现的次数，我们可以很容易地找到能够形成好数对的所有索引组合，从而简化了问题的复杂性。

在实现中，我们通过使用列表推导式 `[x - i for i, x in enumerate(nums)]` 生成 arr 数组，确保每个元素正确地计算为 nums[i] - i。然后使用 Python 的 `Counter` 类从 collections 模块来统计 arr 中每个值的出现次数。`Counter` 是一个专为计数优化的字典结构，它可以准确并有效地统计数组中每个值的频率，从而防止计数错误。

使用 `Counter` 来统计元素的出现次数是相对高效的，因为它的操作基本上是线性时间复杂度 O(n)，其中 n 是数组的长度。然而，如果 `nums` 数组非常大或 arr 中的值范围非常广，`Counter` 所使用的内存可能会成为考虑的问题。尽管如此，在大多数情况下，这种方法因其编码简便和运行时效率而被认为是合适的。如果遇到极端大数据量或内存限制问题，可能需要考虑使用更高效的数据结构或优化算法。

是的，当 `nums[i] - i` 的某个值在 arr 中只出现一次时，它不可能与任何其他元素形成好数对，因为好数对需要至少两个索引的 `nums[i] - i` 值相等。因此，在计算可能的好数对时，我们只考虑那些出现至少两次的值。对于这些值，我们使用公式 v * (v - 1) / 2 计算出其形成好数对的数量，并将这些数量从所有可能的数对总数中减去，从而得出坏数对的数量。如果一个值只出现一次，它不会增加好数对的数量，因此不会影响坏数对的计算。