统计坏数对的数目-LeetCode

2364. 统计坏数对数目

🎯 问题描述（来源于LeetCode）

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

说明：

• 这是一个哈希表计数结合补集思想的问题。

• 直接思考：判断 j - i != nums[j] - nums[i] 比较麻烦。

• 转换思考：

  • 不等式 j - i != nums[j] - nums[i] 等价于 nums[i] - i != nums[j] - j。
  • 反之，好数对满足 j - i == nums[j] - nums[i]，即 nums[i] - i == nums[j] - j。

• 策略：

  1. 计算所有可能的数对总数 $Total$。
  2. 计算满足 nums[i] - i == nums[j] - j 的好数对数量 $Good$。
  3. 答案即为 $Total - Good$。

• 示例：

• 示例 1：

输入：nums = [4,1,3,3]
输出：5
解释：
- 总对数：C(4,2) = 6。
- 检查好数对（nums[i]-i == nums[j]-j）：
  - i=0, val=4, diff=4-0=4
  - i=1, val=1, diff=1-1=0
  - i=2, val=3, diff=3-2=1
  - i=3, val=3, diff=3-3=0
- 只有 (1, 3) 的差值都是 0，是好数对。Good = 1。
- 坏数对 = 6 - 1 = 5。

💻 解题思路

思路1：补集思想 + 哈希表

思路1：代码实现

class Solution:
    def countBadPairs(self, nums: List[int]) -> int:
        # 1. 统计“好数对”的数量
        # 好数对满足：nums[j] - nums[i] == j - i
        # 移项变形为：nums[i] - i == nums[j] - j
        # 我们定义 key = i - nums[i] (或者 nums[i] - i，只要统一即可)
        
        count = defaultdict(int)
        good_pairs = 0 
        
        for i, num in enumerate(nums):
            key = i - num
            
            # 如果之前出现过相同的 key，说明可以组成好数对
            # 累加之前出现的次数
            good_pairs += count[key]
            
            # 更新计数
            count[key] += 1
            
        # 2. 计算所有可能的数对总数
        # 从 l 个元素中选 2 个：C(l, 2) = l * (l - 1) / 2
        l = len(nums)
        total_pairs = l * (l - 1) // 2
        
        # 3. 坏数对 = 总数对 - 好数对
        return total_pairs - good_pairs

思路1：📊 性能分析

• 时间复杂度：$O(N)$
  • 其中 $N$ 是数组 nums 的长度。
  • 遍历数组一次进行哈希表统计，耗时 $O(N)$。
  • 计算总数对耗时 $O(1)$。
  • 总时间复杂度为 $O(N)$。
• 空间复杂度：$O(N)$
  • 哈希表 count 在最坏情况下存储 $N$ 个不同的键值。

思考

1. 数学变换（核心）：

   • 题目给出的条件是 j - i != nums[j] - nums[i]。
   • 直接统计“不等于”的情况很难，因为每个不等的数对差值都不一样。
   • 但是统计“等于”的情况（好数对）很容易：nums[j] - j == nums[i] - i。
   • 我们将每个元素的 index - value 作为特征值。只要特征值相同，就是好数对。

2. 补集思想：

   • 全集 $U$ 是所有可能的 $(i, j)$ 组合，其中 $i < j$。总数为 $C_N^2$。
   • 子集 $A$ 是好数对。
   • 目标集合 $B$ 是坏数对。
   • $B = U - A$。

3. 累加计数法：

   • 在遍历过程中，good_pairs += count[key] 利用了累加技巧。
   • 假设某个 key 之前出现了 $k$ 次，当前是第 $k+1$ 次。
   • 当前元素可以和之前的 $k$ 个元素分别组成好数对，所以增加 $k$ 个。

4. 边界情况：

   • 数组长度为 1：总数对为 0，好数对为 0，结果为 0。
   • 所有元素都相同：例如 [2,2,2]。
     • i=0, key=-2
     • i=1, key=-1
     • i=2, key=0
     • 所有 key 不同，好数对为 0，坏数对 = 总数对。