leetcode-2364

题目

https://leetcode.cn/problems/count-number-of-bad-pairs/description/?envType=daily-question&envId=2025-04-18

分析

• 数据规模10⁵, 暴力双循环必然超时
• 如果 i < j 且 j - i != nums[j] - nums[i],ij是一个坏数对
• 所以好数对的定义是 ：i - nums[i] == j- nums[j]
  • 找好数对
  • 总数量 n*(n-1)/2
  • 坏数对 = 总数量 - 好数对
  • 一次遍历，时间复杂度O(n),空间复杂度O(n)

源代码

https://github.com/Norton-Lin/algorithm/blob/master/go/src/leetcode_2364/2025_04_18_2364.go