Leetcode2364.统计坏数对的数目

链接直达

1. 题目描述

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

2. 分析

核心思路：逆向思考，坏数对是不等关系，转化为相等关系，可以利用hash表等作记忆化前缀值，降维时间复杂度。

翻译：

1. 坏数对表示：

• i < j 且 j-i != nums[j] - nums[i]

• j > i 且 j-i != nums[j] - nums[i] => i-j != nums[i] - nums[j]

2. 上述具备对称性质，所以坏数对实际：

• 任意两个索引i，j，满足 i-j != nums[i]-nums[j] 的数对

正向思考：

• 需要找到所有的数对i，j，进行判断，时间复杂度O(n^2)

逆向思考：

由于坏数对是非等值关系，我们可以定义"好数对"，找等值关系

好数对：

任意两个索引i, j, 满足 i-j == nums[i] - nums[j]

移项：上式等价于 i-nums[i] == j-nums[j]

转化为了 ai = i-nums[i] 找所有索引相同的ai

时间复杂度：O(n)

3. 代码

func countBadPairs(nums []int) int64 {
	// 首先，计算所有数对 (cn2)
	n := len(nums)
	ans := cn2(n)
	// 通过map，聚合相同的ai的索引
	hs := map[int]int{}
	for i, v := range nums {
		hs[v-i]++
	}
	// 遍历hs，拿到好数对数目
	well := 0
	for _, cnt := range hs {
		well += cn2(cnt)
	}
	// 总
	return int64(ans - well)
}

func cn2(n int) int {
	if n < 2 {
		return 0
	}
	return n * (n - 1) / 2
}

上述代码，需要再遍历组，获取好数对，可以做前缀值记忆化，参考两数之和。

func countBadPairs(nums []int) int64 {
	// 首先，计算所有数对 (cn2)
	n := len(nums)
	ans := cn2(n)
	// 通过map，聚合相同的ai的索引
	hs := map[int]int{}
	for i, v := range nums {
		ans -= hs[v-i]
		hs[v-i]++
	}
	return int64(ans)
}

func cn2(n int) int {
	if n < 2 {
		return 0
	}
	return n * (n - 1) / 2
}