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^5
  • 1 <= nums[i] <= 10^9

解题思路

这道题可以通过数学变换巧妙解决。我们需要统计满足 j - i != nums[j] - nums[i] 的数对 (i, j)。

核心观察： 将条件进行变换：

  • j - i != nums[j] - nums[i]
  • 移项得：j - nums[j] != i - nums[i]
  • 即：nums[i] - i != nums[j] - j

这意味着如果两个位置的 nums[k] - k 值相同，那么这两个位置组成的就是"好数对"。

解题思路：

  1. 正向思考：直接统计坏数对比较复杂
  2. 反向思考：先统计好数对，用总数对减去好数对就是坏数对
  3. 核心转换：对于每个位置 i，计算 nums[i] - i 的值
  4. 哈希统计：使用哈希表统计每个 nums[i] - i 值出现的次数
  5. 计算好数对：对于出现 cnt 次的相同值，好数对数量为 cnt * (cnt - 1) / 2

总数对数量为 n * (n - 1) / 2，减去好数对就是答案。

时间复杂度 O(n)，空间复杂度 O(n)。

代码实现

class Solution {
public:
    long long countBadPairs(vector<int>& nums) {
        int n = nums.size();
        unordered_map<int, int> count;
        
        // 统计每个 nums[i] - i 值的出现次数
        for (int i = 0; i < n; i++) {
            count[nums[i] - i]++;
        }
        
        // 计算好数对的数量
        long long goodPairs = 0;
        for (auto& [val, cnt] : count) {
            goodPairs += (long long)cnt * (cnt - 1) / 2;
        }
        
        // 总数对数量减去好数对数量
        long long totalPairs = (long long)n * (n - 1) / 2;
        return totalPairs - goodPairs;
    }
};

class Solution:
    def countBadPairs(self, nums: List[int]) -> int:
        from collections import Counter
        
        n = len(nums)
        # 统计每个 nums[i] - i 值的出现次数
        count = Counter(nums[i] - i for i in range(n))
        
        # 计算好数对的数量
        good_pairs = sum(cnt * (cnt - 1) // 2 for cnt in count.values())
        
        # 总数对数量减去好数对数量
        total_pairs = n * (n - 1) // 2
        return total_pairs - good_pairs

public class Solution {
    public long CountBadPairs(int[] nums) {
        int n = nums.Length;
        Dictionary<int, int> count = new Dictionary<int, int>();
        
        // 统计每个 nums[i] - i 值的出现次数
        for (int i = 0; i < n; i++) {
            int key = nums[i] - i;
            count[key] = count.GetValueOrDefault(key, 0) + 1;
        }
        
        // 计算好数对的数量
        long goodPairs = 0;
        foreach (int cnt in count.Values) {
            goodPairs += (long)cnt * (cnt - 1) / 2;
        }
        
        // 总数对数量减去好数对数量
        long totalPairs = (long)n * (n - 1) / 2;
        return totalPairs - goodPairs;
    }
}

/**
 * @param {number[]} nums
 * @return {number}
 */
var countBadPairs = function(nums) {
    const n = nums.length;
    const count = new Map();
    
    // 统计每个 nums[i] - i 值的出现次数
    for (let i = 0; i < n; i++) {
        const key = nums[i] - i;
        count.set(key, (count.get(key) || 0) + 1);
    }
    
    // 计算好数对的数量
    let goodPairs = 0;
    for (const cnt of count.values()) {
        goodPairs += cnt * (cnt - 1) / 2;
    }
    
    // 总数对数量减去好数对数量
    const totalPairs = n * (n - 1) / 2;
    return totalPairs - goodPairs;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型分析
时间复杂度O(n) - 需要遍历数组一次进行统计，然后遍历哈希表计算结果
空间复杂度O(n) - 哈希表存储不同的 nums[i] - i 值，最坏情况下所有值都不同

相关题目