532.md

Question:

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].

Analysis

这题给定一个无序的数组，让找其中两个差值等于给定值的组数。首先想到的，应当是将数组遍历建立hash，比如给定的是[1, 3]，差值是2，为了避免重复计算，我们求1的符合条件的数时，那就找是否有3或者-1存在，存在就加一，然后找3符合的值，就是5或者1，存在就加一，那么这对数算了两遍了，最后结果就要除以2.当差值为0时候，只要某个数出现的个数大于1（大于等于2），就可以了。如果差值为负数，由题目意思可知，这不可能，差值的绝对值怎会为负数呢，故直接返回0.这就是解法一。

思考下解法一，如果我们在遍历hash的时候，都是默认找比当前值大的，比如[1, 3]，k=2，给1找的时候，那就找（1+2）是否存在，给3找的时候，就找（3+5），这样所有的结果都算了，也不会重复，还简单明了，如此，固定了顺序，还是不错的，这就是解法二。

Tips

无序中的有序比较值得推荐。

Code

// 解法一
func findPairs1(nums []int, k int) int {
	if k < 0 {
		return 0
	}

	mapping := make(map[int]int)
	for _, v := range nums {
		mapping[v]++
	}

	var ret int
	for value, count := range mapping {
		if k == 0 {
			if count > 1 {
				ret += 2
			}
			continue
		}

		t1 := value - k
		t2 := value + k
		if mapping[t1] != 0 {
			ret++
		}
		if mapping[t2] != 0 {
			ret++
		}
	}
	return ret / 2
}

// 解法二
func findPairs(nums []int, k int) int {
	ans, m := 0, make(map[int]int)
	for _, v := range nums {
		m[v]++
	}
	for n, v := range m {
		if k < 0 {
			return ans
		} else if k == 0 && v >= 2 {
			ans++
		} else if k > 0 && m[n+k] > 0 {
			ans++
		}
	}
	return ans
}