「每日LeetCode」2020年12月17日

本文最后更新于：2023年3月19日 晚上

Lt1512. 好数对的数目

1512. 好数对的数目

难度简单 45 收藏分享切换为英文接收动态反馈
给你一个整数数组 nums 。
如果一组数字 (i,j) 满足 nums[i] == nums[j] 且 i < j ，就可以认为这是一组 好数对 。
返回好数对的数目。
 示例 1：

1
2
3
输入：nums = [1,2,3,1,1,3]
输出：4
解释：有 4 组好数对，分别是 (0,3), (0,4), (3,4), (2,5) ，下标从 0 开始

示例 2：

1
2
3
输入：nums = [1,1,1,1]
输出：6
解释：数组中的每组数字都是好数对

示例 3：

1
2
输入：nums = [1,2,3]
输出：0

提示：

  • 1 <= nums.length <= 100
  • 1 <= nums[i] <= 100

思路

使用桶计数法，求完之后，筛选出长度大于 1 的数组，对每个数组进行求取 2 个元素的组合数相加即为答案。

解答

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
/**
 * @param {number[]} nums
 * @return {number}
 */
var numIdenticalPairs = function (nums) {
  const map = {};
  for (let i = 0; i < nums.length; i++) {
    if (map[nums[i]]) map[nums[i]].push(i);
    else map[nums[i]] = [i];
  }
  const fact = (n) => {
    let sum = 1;
    for (let i = 2; i <= n; i++) sum *= i;
    return sum;
  };
  const combine = (n) => fact(n) / (fact(2) * fact(n - 2));
  let res = 0;
  for (const item of [...Object.values(map)])
    if (item.length > 1) res += combine(item.length);
  return res;
};