[LeetCode] 每日一题 2364. 统计坏数对的数目（逆向思维）

题目描述

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

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

题目链接

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

示例输入

示例 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

解题思路

这道题乍一看条件有点复杂，要求我们找出所有满足 i < j 且 j - i != nums[j] - nums[i] 的数对 (i, j)，看起来不像是能用常规方法快速判断的题。

但如果我们稍微整理一下条件，其实可以将其变形为nums[j] - j ≠ nums[i] - i

这就好处理多了！换个角度思考，如果我们先计算出所有的数对数量，然后再减去那些“不是坏数对”的数量（即 nums[j] - j == nums[i] - i 的数量），我们就能得到答案。这是一种逆向思维，思路更清晰 ✨

具体来说：

• 所有数对的总数是 n * (n - 1) / 2，这是一个从0到n-1的等差数列求和

• 然后我们用哈希表统计每个 nums[i] - i 的出现次数

• 每次遇到重复的值，就说明遇到一个“不是坏数对”的组合，就从总数中减去

• 剩下的，就是“坏数对”的数量了

代码实现

class Solution {
    public long countBadPairs(int[] nums) {
        HashMap<Integer, Integer> count = new HashMap<>();
        int n = nums.length;
        long ans = (long)(n - 1) * n / 2; // 所有数对总数
        for (int i = 0; i < n; i++) {
            int cnt = count.getOrDefault(nums[i] - i, 0);
            ans -= cnt; // 减去“不是坏数对”的数量
            count.put(nums[i] - i, cnt + 1);
        }
        return ans;
    }
}

复杂度分析

• 时间复杂度：O(n)，一次遍历数组，同时进行哈希计数，效率非常高 🚀；

• 空间复杂度：O(n)，最坏情况下每个 nums[i] - i 都唯一，需要记录 n 个键值对；

这也是经典的**“总数减去符合条件数 = 不符合条件数”**的逆向套路，在处理复杂条件计数时非常有用 💡

总结

这题非常适合训练我们从“正向暴力枚举”切换到“逆向优化”的思维方式。如果直接枚举所有数对判断是否为“坏数对”，时间复杂度会达到 O(n^2)，但换个角度，把问题转换为“总数减去好数对数”，就可以轻松在 O(n) 内解决。这种技巧在面试中经常遇到，非常值得记住 🧠

希望这篇分享能为你带来启发！如果你有任何问题或建议，欢迎在评论区留言，与我共同交流探讨。