算法----好数对的数目(Kotlin)

题目

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

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/number-of-good-pairs
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

解决思路

1.按照题意 暴力求解

2.使用Map 统一每个数出现的次数
假如有三个1 1 1 那么他们的好数对为 0 1 2 结果为0 + 1 + 2 根据高斯定理 结果应该为 3* （3-1） /2

即公式v * (v - 1) / 2

3.对方法2 优化一次 减少一次遍历

解决方法

方法一：

    fun numIdenticalPairs(nums: IntArray): Int {
        var result = 0
        nums.forEachIndexed { index, _ ->
            for (j in index + 1 until nums.size) {
                if (nums[j] == nums[index]) {
                    result++
                }
            }
        }
        return result
    }

1
2
3
4
5
6
7
8
9
10
11
12

方法二：

    fun numIdenticalPairs2(nums: IntArray): Int {
        var result = 0
        var map = HashMap<Int, Int>()
        nums.forEachIndexed { _, i ->
            map[i] = map[i]?.plus(1) ?: 1
        }
        map.values.forEachIndexed { index, i ->
            result += i * (i - 1) / 2
        }
        return result
    }
1
2
3
4
5
6
7
8
9
10
11

方法三：

    fun numIdenticalPairs3(nums: IntArray): Int {
        var result = 0
        var map = HashMap<Int, Int>()
        nums.forEachIndexed { _, i ->
            map[i] = map[i]?.plus(1) ?: 0
            result+= map[i]!!
        }
        return result
    }
1
2
3
4
5
6
7
8
9

总结

1.周末愉快

2.很多事确实不如意 但是生活还是要继续
如果一件事因为不可抗力实在没有办法做
那么是不是可以换个思路 做其他的事情呢

加油