力扣每日打卡 2364. 统计坏数对的数目 (中等)

前言

这是刷算法题的第十四天，用到的语言是JS
题目：力扣 2364. 统计坏数对的数目 (中等)

一、题目内容

给你一个下标从 $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. 哈希函数1

代码如下（实例）：

/**
 * @param {number[]} nums
 * @return {number}
 */
var countBadPairs = function(nums) {
  const len = nums.length
  const map = new Map()
  let goodPairs = 0
  
  // 遍历数组，统计 i - nums[i] 相等的数量
  // 1. 使用一个哈希表（对象）来记录每个 i - nums[i] 的出现次数。
  // 2. 遍历数组，对每个j，计算 j - nums[j]，检查之前已经记录的 i - nums[i] 的数量。
  // 3. 对当前 j 的 j - nums[j] 进行统计，用以计算坏数对的数量。
  for (let i = 0; i < len; i++) {
      const currentKey = i - nums[i]
      goodPairs += map.get(currentKey) || 0
      map.set(currentKey, (map.get(currentKey) || 0) + 1) // map对于相同的键，只会更新值，这就是为什么要 +1
  }
  
  // 总数对减去好数对就是坏数对  总数对就是 n * (n - 1) / 2，数列的求和公式
  return (len * ((len - 1) / 2)) - goodPairs
}

2. 哈希函数2

代码如下（示例）：

/**
 * @param {number[]} nums
 * @return {number}
 */
var countBadPairs = function(nums) {
  const len = nums.length
  const map = new Map()
  let goodPairs = 0
  
  // 遍历数组，统计 i - nums[i] 相等的数量
  // 1. 使用一个哈希表（对象）来记录每个 i - nums[i] 的出现次数。
  // 2. 遍历数组，对每个j，计算 j - nums[j]，检查之前已经记录的 i - nums[i] 的数量。
  // 3. 对当前 j 的 j - nums[j] 进行统计，用以计算坏数对的数量。
  for (let i = 0; i < len; i++) {
      const currentKey = i - nums[i]

      if(map.has(currentKey)) {
        goodPairs += map.get(currentKey)
        // break // 此处能不能break呢，就算当前位置有，也要加上当前位置，所以不能
      }
      map.set(currentKey, (map.get(currentKey) || 0) + 1 )
  }
  
  // 总数对减去好数对就是坏数对  总数对就是 n * (n - 1) / 2，数列的求和公式
  return (len * ((len - 1) / 2)) - goodPairs
}

2.官方题解

2.1 方法一：使用 sqrt 函数

代码如下（示例）：

var countBadPairs = function(nums) {
    const mp = new Map();
    let res = 0;
    for (let i = 0; i < nums.length; i++) {
        const key = nums[i] - i;
        res += i - (mp.get(key) || 0);
        mp.set(key, (mp.get(key) || 0) + 1);
    }
    return res;
};

作者：力扣官方题解
链接：https://leetcode.cn/problems/count-number-of-bad-pairs/solutions/3638890/tong-ji-pi-shu-dui-de-shu-mu-by-leetcode-04ya/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

复杂度分析：

时间复杂度： $O(n)$，其中 $n$ 是 $nums$ 的长度。使用哈希表插入和查询的时间复杂度是 $O(1)$，总共遍历 $n$ 个元素，因此时间复杂度为 $O(n)$。

空间复杂度： $O(n$)。哈希表的空间复杂度是 $O(n)$。

链接：力扣本题官方题解
来源：力扣（LeetCode）