2364. 统计坏数对的数目

🟠   🔖  数组 哈希表 数学 计数  🔗 力扣 LeetCode

题目

You are given a 0-indexed integer array nums. A pair of indices (i, j) is a bad pair if i < j and j - i != nums[j] - nums[i].

Return _the total number ofbad pairs in _nums.

Example 1:

Input: nums = [4,1,3,3]

Output: 5

Explanation: The pair (0, 1) is a bad pair since 1 - 0 != 1 - 4.

The pair (0, 2) is a bad pair since 2 - 0 != 3 - 4, 2 != -1.

The pair (0, 3) is a bad pair since 3 - 0 != 3 - 4, 3 != -1.

The pair (1, 2) is a bad pair since 2 - 1 != 3 - 1, 1 != 2.

The pair (2, 3) is a bad pair since 3 - 2 != 3 - 3, 1 != 0.

There are a total of 5 bad pairs, so we return 5.

Example 2:

Input: nums = [1,2,3,4,5]

Output: 0

Explanation: There are no bad pairs.

Constraints:

• 1 <= nums.length <= 10^5
• 1 <= nums[i] <= 10^9

题目大意

给你一个下标从** 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

解题思路

1. 总数对数量计算

   • 数组长度为 n，总数对的数量为 total = n * (n - 1) / 2。

2. 转换为差值问题

   • 由于判断条件是 nums[j] - nums[i] ≠ j - i，可以等价转化为：nums[j] - j ≠ nums[i] - i
   • 定义 diff[i] = nums[i] - i，我们只需要统计差值相等的数对，即好数对。

3. 哈希计数

   • 使用 Map 记录 diff 的频次统计。
   • 对每个相同的 diff 值 value，能形成的好数对数量为 success = value * (value - 1) / 2。

4. 返回结果

   • 坏数对的总数目即总数对减去好数对的值：total - success

复杂度分析

• 时间复杂度：O(n)，遍历数组并统计频次，哈希查找和更新为常数时间复杂度。
• 空间复杂度：O(n)，需要额外的哈希表空间。

代码

/**
 * @param {number[]} nums
 * @return {number}
 */
var countBadPairs = function (nums) {
	const n = nums.length;
	const total = (n * (n - 1)) / 2;
	let success = 0;

	let count = new Map();
	for (let i = 0; i < n; i++) {
		const diff = nums[i] - i;
		count.set(diff, (count.get(diff) || 0) + 1);
	}
	for (let value of count.values()) {
		success += (value * (value - 1)) / 2;
	}
	return total - success;
};

相关题目

题号	标题	题解	标签	难度	力扣
532	数组中的 k-diff 数对		数组 哈希表 双指针 2+	🟠	🀄️ 🔗
974	和可被 K 整除的子数组		数组 哈希表 前缀和	🟠	🀄️ 🔗
1814	统计一个数组中好对子的数目		数组 哈希表 数学 1+	🟠	🀄️ 🔗
2006	差的绝对值为 K 的数对数目	[✓]	数组 哈希表 计数	🟢	🀄️ 🔗
2176	统计数组中相等且可以被整除的数对	[✓]	数组	🟢	🀄️ 🔗
2426	满足不等式的数对数目		树状数组 线段树 数组 4+	🔴	🀄️ 🔗