链接直达

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表等作记忆化前缀值,降维时间复杂度。

翻译:

  1. 坏数对表示:

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

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

  1. 上述具备对称性质,所以坏数对实际:

  • 任意两个索引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
}