脚撕LeetCode(1512)Easy
题目地址：https://leetcode-cn.com/problems/number-of-good-pairs/
给你一个整数数组 nums 。 如果一组数字 (i,j) 满足 nums[i] == nums[j] 且 i < j ，就可以认为这是一组 好数对 。 返回好数对的数目。
示例 1：
输入：nums = [1,2,3,1,1,3]
输出：4
解释：有 4 组好数对，分别是 (0,3), (0,4), (3,4), (2,5) ，下标从 0 开始
示例 2：
输入：nums = [1,1,1,1]
输出：6
解释：数组中的每组数字都是好数对
示例 3：
输入：nums = [1,2,3]
输出：0
提示：
1 <= nums.length <= 100
1 <= nums[i] <= 10这道题的题意，简单来说就是同一个数字两两组对的排列组合。
高中学过一个公式，比如一个数出现的次数有n那么排列组合就是n-1 + n-2 + …… 1。简化= (n-1) * (n) / 2
一、爆破法
这里直接用map统计一个数字出现的次数，然后再循环一次直接用我们的公式计算出每个数字的排列组合，最后+起来返回。
执行结果如下：
48 / 48 个通过测试用例
状态：通过
执行用时: 1 ms
内存消耗: 35.7 MB
public static int numIdenticalPairsMe(int[] nums) {
Map<Integer,Integer> map = new HashMap<>();
for (int item : nums) {
map.put(item, map.getOrDefault(item, 0) + 1);
}
int ans = 0;
int item = 0;
for (Map.Entry<Integer,Integer> entry : map.entrySet()) {
item = entry.getValue();
ans += (item - 1) * item / 2;
}
return ans;
}这里我是想过用数组的，但是人家说了nums[i] <= 100 ,nums.length <=100 所以这个数组要有100，但是这么做我感觉收益不大，就还是用的map（没想到我以为总是我以为hhhhhh）
下面放出评论区大佬跟我类似思路的实现：
二、数组法
执行结果如下：
48 / 48 个通过测试用例
状态：通过
执行用时: 0 ms
内存消耗: 35.9 MB
public int numIdenticalPairs(int[] nums) {
int[] cs = new int[101];
int count = 0;
//记录不同元素的重复数量
for(int num : nums){
cs[num] += 1;
}
for(int c :cs ){
if(c > 1){
// n 的方程
count += (c*(c-1))/2;
}
}
return count;
}数组法的内存和我的差不多，但是时间却是0ms，我是1ms，所以其实经常我以为还是只是我以为，数组和map的大小差别并没有想象中那么小。
本文参与 腾讯云自媒体同步曝光计划，分享自微信公众号。
原始发表：2021-06-15，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
腾讯云开发者
