K-diff Pairs in an Array

Given an array of integers and an integer k, you need to find the number of unique k-diff pairs in the array. Here a k-diff pair is defined as an integer pair (i, j), where i and j are both numbers in the array and their absolute difference is k.

Example 1:

Input: [3, 1, 4, 1, 5], k = 2
Output: 2
Explanation: There are two 2-diff pairs in the array, (1, 3) and (3, 5).
Although we have two 1s in the input, we should only return the number of unique pairs.

Example 2:

Input:[1, 2, 3, 4, 5], k = 1
Output: 4
Explanation: There are four 1-diff pairs in the array, (1, 2), (2, 3), (3, 4) and (4, 5).

Example 3:

Input: [1, 3, 1, 5, 4], k = 0
Output: 1
Explanation: There is one 0-diff pair in the array, (1, 1).

Note:

1. The pairs (i, j) and (j, i) count as the same pair.
2. The length of the array won’t exceed 10,000.
3. All the integers in the given input belong to the range: [-1e7, 1e7].

提示	解題應用
TwoPointers	巢狀回圈
Array	Array/Slice

Default:

func findPairs(nums []int, k int) int {

}

解答思路:

這邊要從一陣列中找任兩值距離為k的共有幾組，最簡單的方式就是用巢狀迴圈都從同一陣列來取資料並兩兩比較，因為(x, y)與(y, x)這種組合只算一種，換句話說只存兩值相減距離為正數(也就是k)的結果就行了，所以當兩個值並非陣列中的相同index且相減為正數就儲至hashmap之中，最後直接回傳hashmap長度即可，至於為什麼是存在hashmap中而非直接計數，原因在於兩相同的值就會只被算到一次(key值一樣)。

程式碼解說:

一開始先判斷k是否為負數，如果是就直接回傳0，接下來就初始化一hashmap，其中key值為陣列中某一個元素儲存的值而value則是另一個陣列中對應的值，接著便是用巢狀迴圈都從同一陣列來取資料，如果分別取出的值並非陣列中的同一個位置(index)，且兩值相減為k就存儲至hashmap之中，key與value則分別對應兩個取出的值，最後回傳hashmap的長度就會是結果

if k < 0 {
	return 0
}
hashMap := make(map[int]int)
for i, vi := range nums {
	for j, vj := range nums {
		if i != j && vi-vj == k {
			hashMap[vi] = vj
		}
	}
}
return len(hashMap)

完整程式碼:

func findPairs(nums []int, k int) int {
	if k < 0 {
		return 0
	}
	hashMap := make(map[int]int)
	for i, vi := range nums {
		for j, vj := range nums {
			if i != j && vi-vj == k {
				hashMap[vi] = vj
			}
		}
	}
	return len(hashMap)
}

總結:

要從一陣列中找任兩值距離為k的共有幾組((x, y)與(y, x)只算一種)，最簡單的方式就是用巢狀迴圈都從同一陣列來取資料並兩兩比較，當兩個值並非陣列中的相同index且相減距離為正數k就儲至hashmap(兩相同的值只會被算到一次)之中，最後直接回傳hashmap長度即可。