今日题目

https://leetcode.com/problems/count-number-of-bad-pairs/description/

解题思路

本题的关键在于：找出那些下标差与元素差相等的数对。

如果我们将两个数之间的距离减去下标差，结果相等的就是"好数对"。

即：$j - i = nums[j] - nums[i] \Longrightarrow nums[j] - j = nums[i] - i$。

这样问题就变简单了：对数组中每个元素减去其下标，然后统计有多少对 i, j 使得转换后的值相同（即"好数对"的数量）。

最后用总数对数减去好数对数，即可得到坏数对的数目。

解题步骤

  1. 计算所有数对的总数，即 $N \times (N - 1) / 2$，N 为数组长度。
  2. 对每个 nums[i] 减去其下标 i。
  3. 统计转换后值相同的数对数量（即好数对）。
  4. 用总数对数减去好数对数，得到坏数对数目。

复杂度分析

  • 时间复杂度：$O(N)$，N 为数组长度。

  • 空间复杂度：$O(N)$，N 为数组长度。

代码

class Solution:
    def countBadPairs(self, nums: List[int]) -> int:
        nums = [nums[i] - i for i in range(len(nums))]
        cnt = Counter(nums)
        N = len(nums)
        ans = N * (N - 1) // 2
        for v in cnt.values():
            ans -= v * (v - 1) // 2

        return ans

image.png