当前位置：首页 > ds >正文

LeetCode 2364.统计坏数对的数目：反向统计

ds 2025/7/22 8:24:17

【LetMeFly】2364.统计坏数对的数目：反向统计

力扣题目链接：https://leetcode.cn/problems/count-number-of-bad-pairs/

给你一个下标从 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⁵
1 <= nums[i] <= 10⁹

很不错的一道题。

解题方法：哈希表反向计数

长度为 $n$ 的数组一共有多少个数对？

一共有 $n (n - 1) /2$ 个。

其中有多少个坏数对？

总数对个数减去好数对个数即为坏数对个数。

如何统计有多少个好数对个数？

$n u m s [j] - n u m s [i] == j - i$ 等价于 $n u m s [j] - j == n u m s [i] - i$ ，

我们可以将数组中的每个数减去它的下标，问题就变成了“数组中相同的数组成的数对有多少个”。

数组中相同的数组成的数对有多少个？

可以使用一个哈希表统计每种元素出现的次数。假设遍历处理过的数组时遍历到了 $x$ ，那么当前 $x$ 可以与已出现过的所有 $x$ 配对。

问题解决。

时间复杂度 $O (l e n (n u m s))$
空间复杂度 $O (l e n (n u m s))$

AC代码

C++

/** @Author: LetMeFly* @Date: 2025-04-18 10:23:46* @LastEditors: LetMeFly.xyz* @LastEditTime: 2025-04-18 10:25:58*/
#if defined(_WIN32) || defined(__APPLE__)
#include "_[1,2]toVector.h"
#endiftypedef long long ll;class Solution {
public:long long countBadPairs(vector<int>& nums) {unordered_map<int, int> times;ll ans = nums.size() * (nums.size() - 1) / 2;for (int i = 0; i < nums.size(); i++) {ans -= times[nums[i] - i]++;}return ans;}
};

Python

'''
Author: LetMeFly
Date: 2025-04-18 10:26:49
LastEditors: LetMeFly.xyz
LastEditTime: 2025-04-18 10:28:15
'''
from typing import List
from collections import defaultdictclass Solution:def countBadPairs(self, nums: List[int]) -> int:times = defaultdict(int)ans = len(nums) * (len(nums) - 1) // 2for i, v in enumerate(nums):ans -= times[v - i]times[v - i] += 1return ans

Java

/** @Author: LetMeFly* @Date: 2025-04-18 10:29:32* @LastEditors: LetMeFly.xyz* @LastEditTime: 2025-04-18 10:34:19*/
import java.util.Map;
import java.util.HashMap;class Solution {public long countBadPairs(int[] nums) {long ans = (long)nums.length * (nums.length - 1) / 2;Map<Integer, Integer> times = new HashMap<>();for (int i = 0; i < nums.length; i++) {ans -= times.merge(nums[i] - i, 1, Integer::sum) - 1;}return ans;}
}

Go

/** @Author: LetMeFly* @Date: 2025-04-18 10:35:10* @LastEditors: LetMeFly.xyz* @LastEditTime: 2025-04-18 10:38:47*/
package mainfunc countBadPairs(nums []int) int64 {ans := len(nums) * (len(nums) - 1) / 2times := map[int]int{}for i, v := range nums {ans -= times[v - i]times[v - i]++}return int64(ans)
}