# 1512. Number of Good Pairs

## [題目:](https://leetcode.com/problems/number-of-good-pairs/)

給定一個一維陣列，要找出陣列裡含有幾個Good Pair，
Good Pair為數值相同且順序由前至後的兩個數，
就是要找出有幾個值為相同的配對。

## 思路一

順著題目意思往下解，雙迴圈由前置後，有相同值就累加一

func numIdenticalPairsV1(nums []int) int {
	var count = 0
	for i := 0; i < len(nums); i++ {
		for j := 0; j < i; j++ {
			if nums[i] == nums[j] {
				count++
			}
		}
	}
	return count
}

## 思路二

如果輸入是[1]，輸出為 0
如果輸入是[1,1]，輸出為 1 (+1)
如果輸入是[1,1,1]，輸出為 3 (+2)
如果輸入是[1,1,1,1]，輸出為 6 (+3)
...

題目可以改為由前至後 有哪幾種排列組合的可能，
中間插進了不同的數值不會對排序造成影響。

把總共有幾個相同的值，數量存進map中，
最後再一次做可能性的累加

func numIdenticalPairsV2(nums []int) int {
	var countMap = map[int]int{}
	for _, n := range nums {
		countMap[n] += 1
	}

	var count = 0
	for _, c := range countMap {
		for i := 0; i < c; i++ {
			count += i
		}
	}
	return count
}

但累加的過程還是用到了雙迴圈

## 思路三

為了把雙迴圈去除掉，
找出 0,1,3,6,10 序列的公式，
序列中的第n項值為: n(n-1)/2

func numIdenticalPairsV3(nums []int) int {
	var countMap = map[int]int{}
	for _, n := range nums {
		countMap[n] += 1
	}

	var count = 0
	// In 0:0, 1:1, 2:3, 4:6, 5:10 sequence,
	// the formula is n:n(n-1)/2 where n > 1
	for _, c := range countMap {
		if c > 1 {
			count += c * (c - 1) / 2
		}
	}
	return count
}