Leetcode17-好数对的数目（1512）

1、题目

给你一个整数数组 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] <= 100

2、解

暴力解

    int numIdenticalPairs(vector<int> &nums)
    {
        int result = 0;
        for(int i = 0; i < nums.size() - 1; i++){
            for(int j = i + 1; j < nums.size(); j++){
                if(nums[i] == nums[j]) result++;
            }
        }
        return result;
    }

另解
在题解里边看到的一个绝妙解
思路就是把nums中的每个数据看作temp数组的下标(该下标从1开始, 出现间隙不用管, 比如nums={2, 3, 7}, 对应temp={0, 1, 1, 0, 0 , 0 ,1}), 遍历nums然后把对应temp的位置做++操作记录每个数据出现次数即可, 关于对数的话, 找到规律发现其实就是把每次遍历数据出现次数-1叠加起来。
比如：{2, 3, 7}→{0, 1, 1, 0, 0 , 0 ,1}，好数对为0；
{2, 3, 7，2}→{0, 2, 1, 0, 0 , 0 ,1}，好数对为1。
可以理解为第一次出现的数字就占了萝卜坑了，如果后边再次出现就代表它刚好满足值相等，且出现位置索引值是大于第一次出现该数字的索引值的（遍历顺序本就是从小到大）。

    int numIdenticalPairsA(vector<int> &nums)
    {
        int result = 0;
        int temp[100] = {};
        for(auto num : nums){
            result += temp[num - 1];
            temp[num -1]++;
        }
        return result;
    }