1512.NumberOfGoodPairs.md

解题思路

首先，要考虑good pairs实际上就是找相同元素，因为相同元素找到了，必然是有顺序的。因此，你首先要去找相同元素的个数，看到题目里的限制1 <= nums[i] <= 100很容易想到计数排序，又因为1 <= nums.length <= 100，所以一个桶里面至多装100,用int数组足以解决问题; 其次，假设你有100个相同的1，那么这一组1里面有多少个good pairs呢？ 很容易，你将这100个1按顺序排好（它必然是有先后顺序的，从nums中拿出，只是我们不care它的顺序），那么第一个1与之后的99个1必然有99个good pairs，同理易得，n个相同的数就有C(n, 2) = n * (n-1)/2 或者你直接做个加法(n-1) + (n-2) + ... + 1 = n * (n-1) / 2。 综上，先统计相同元素的个数，然后对每一组计算可能得到的good pairs个数，加起来就ok了。

代码

class Solution {
    public int combinationNumOf2(int n) {
        /*
            计算组合数 C(n, 2) = n * (n-1) / 2;
        */
        return n * (n - 1) /2;
    }

    public int numIdenticalPairs(int[] nums) {
        int goodPairs = 0;
        int len = nums.length;
        int[] bucket = new int[101]; // 借鉴计数排序，统计相同元素个数
        for(int i = 1; i < 101; i++) 
            bucket[i] = 0;
        for (int i = 0; i < len; i++) 
            // if (nums[i] < 101 && nums[i] > 0)
            bucket[nums[i]]++;
        for (int i = 1; i < 101; i++) {
            if (bucket[i] <= 1) // At most only one, no gootPairs of this element
                continue;
            goodPairs += combinationNumOf2(bucket[i]);
        }
        return goodPairs;
    }
}