Java中count[a]++如何统计数组相同元素？LeetCode好数对解法疑问

先明确问题：我们要统计数组中满足**i < j 且 nums[i] == nums[j]**的数对总数。

你的原始解法（双重循环） #

这是最直观的思路：通过两层循环遍历所有i<j的组合，找到相等的元素就计数。代码如下：

public int numIdenticalPairs(int[] nums) {
    int count = 0;
    for(int i=0; i<nums.length; i++){
        for(int j=i+1; j<nums.length; j++){
            if(nums[i]==nums[j]){
                count++;
            }
        }
    }
    return count;
}

这个解法的时间复杂度是O(n²)，当数组规模较大时效率偏低。

优化解法的核心逻辑 #

优化解法利用「计数累加」的思路，把时间复杂度降到O(n)，核心是理解res += count[a]++这一行的作用：

public int numIdenticalPairs(int[] A) {
    int res = 0, count[] = new int[101];
    for (int a: A) {
        res += count[a]++;
    }
    return res;
}

这里的count数组用来统计每个数字之前已经出现过的次数（题目限制数字范围是1~100，所以数组大小设为101足够覆盖所有可能值）。我们逐个遍历数组元素：

• 第一次遇到数字a时，count[a]的值是0，说明之前没有相同数字，不会新增好数对，res加0；之后count[a]自增为1，记录该数字已出现1次。
• 第二次遇到a时，count[a]的值是1，说明之前已有1个a，这个新a能和之前的1个a组成1个好数对，res加1；之后count[a]自增为2。
• 第三次遇到a时，count[a]的值是2，说明之前已有2个a，这个新a能和这2个a各组成一对，新增2个好数对，res加2；之后count[a]自增为3。

以此类推，每遇到一个重复数字，它能贡献的好数对数量就是该数字之前出现过的次数，把这些数量累加起来，就是所有好数对的总数。

举个实际例子验证 #

比如数组[1,2,1,1,3]：

1. 第一个元素1：count[1]=0 → res=0，count[1]变为1
2. 第二个元素2：count[2]=0 → res=0，count[2]变为1
3. 第三个元素1：count[1]=1 → res=0+1=1，count[1]变为2
4. 第四个元素1：count[1]=2 → res=1+2=3，count[1]变为3
5. 第五个元素3：count[3]=0 → res=3，count[3]变为1

最终res=3，对应实际的好数对：(0,2)、(0,3)、(2,3)，完全正确。

这个解法的时间复杂度是O(n)，空间复杂度是O(1)（count数组大小固定），比双重循环高效得多。

内容的提问来源于stack exchange，提问作者Quamrulssss