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 <= 105
1 <= nums[i] <= 109
2. 分析
核心思路:逆向思考,坏数对是不等关系,转化为相等关系,可以利用hash表等作记忆化前缀值,降维时间复杂度。
翻译:
坏数对表示:
i < j 且 j-i != nums[j] - nums[i]
j > i 且 j-i != nums[j] - nums[i] => i-j != nums[i] - nums[j]
上述具备对称性质,所以坏数对实际:
任意两个索引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
}
评论