【Leetcode Daily】2364统计坏数对的数目

题目浅析

• 想查看原题可以点击题目链接。

• 简单地说，就是给了一个坏数对的定义，要求找出坏数对的总数。所谓的坏数对，就是这个整型数组中的两个数，他们的数值之差与下标之差不等就算。（默认差值计算只会是大减小，只会是正数）

思路分享

• 陆爻齐思考了下，发现坏数对的共性，是数值减去下标后，差值不为零的情况，根据昨天所学的列未知量，可以这么看。

• 设两个数值分别为 a 和 b，下标分别为 i 和 j，那么坏数对的定义就是 a-b != i-j，简单变换得 a-i != b-j，也就是各自数值减去下标不相等就算坏数对。

• 这样就变换成了比较熟悉的枚举问题，遍历所有数值与自身下标之差，并记录到哈希表中，同时也统计已遍历个数。每次枚举新的数字，都会查找哈希表中对应的个数，这个个数就是好数对，但是总数对减去这个数字，就是坏数对的个数。这就是陆爻齐的解法（放到参考题解的注释里了）。

• 灵神的解法更直接一些，可以直接计算所有数对的个数（两两组合），然后减去好数对，剩下的就是坏数对的个数了。具体的做法与上面陆爻齐的解法一致。

  https://leetcode.cn/problems/count-number-of-bad-pairs/solutions/1728063/by-endlesscheng-uam3/

代码解答（强烈建议自行解答后再看）

• 参考题解

class Solution:
    def countBadPairs(self, nums: List[int]) -> int:
        res = comb(len(nums), 2) # 计算总数目
        rec = Counter()
        for index, num in enumerate(nums):
            tmp = num - index
            res -= rec[tmp] # 减去好数对
            rec[tmp] += 1
        return res


# class Solution:
#     def countBadPairs(self, nums: List[int]) -> int:
#         res = 0 # 记录坏数对数目
#         total = 0 # 计算已遍历的总数目
#         rec = Counter()
#         index = 0 # 记录当前数组下标
#         for num in nums:
#             tmp = num - index
#             res += total - rec[tmp]
#             total += 1
#             index += 1
#             rec[tmp] += 1
#         return res