统计坏数对的数目

Leetcode Link: 6142. 统计坏数对的数目 - 力扣（LeetCode）

题目

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

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

本题是第 84 场双周赛的T2，没做出来，可以说完全没有头绪。

解法一

思路： 本题的条件是不等式 $j-i\ne nums[i]-nums[j]$

如果闷头考虑这个条件，非常难处理。我在这里就考虑这个问题考虑了半个多小时都不对，来回 debug

故对该不等式移项，改写为 $nums[i]-i\ne nums[j]-j$

于是我们可以用哈希表来记录每一个 $nums[i]-i$ 出现的次数

若直接考虑坏数的情况，则需要对所有不同的 $nums[i]-i$ 进行组合统计，显然，若所有 $nums[i]-i$ 都不同时，时间复杂度为 $O(N^2)$，必超时。

所以我们考虑他的对立问题，即非坏数对 $nums[i]-i==nums[j]-j$ 的个数，再用总数相减即可。

题解：

class Solution:
    def countBadPairs(self, nums: List[int]) -> int:
        dd = defaultdict(int)
        for i, val in enumerate(nums):
            dd[val-i] += 1
        
        res = 0  # 非坏数对个数
        for val in dd.values():
            res += (val*(val-1))//2
            
        n = len(nums)
        total = n * (n-1) // 2 # 总对数
        
        return total - res

解法二

思路：

题解：

解法三

思路：

题解：

启发和联系