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

---

给定一个数组，问数组中绝对差值为k的unique数对有多少个。 注意数对不能有重复，比如第一个样例，虽然有两个1，但是2-diff的数对(1,3)只能算一个。 我使用的方法非常简单直白。首先因为绝对误差肯定是非负数，所以如果k<0，则直接返回0对。 然后如果k==0，则说明数对中的两个数必须相等，所以对于k==0的情况，只需要统计一下数组中有多少个重复的数。 如果k>0，则对于每一个数num，如果num+k也在数组中，则找到一个k-diff的数对。 所以为了方便查找和统计，我们首先把数和频率统计到一个map中，边map，可以边统计重复数字个数repeated。 如果k==0，直接返回repeated。 否则把map的key放到一个新的vector中，根据map的性质，这个新的vector是sorted的。则遍历sorted数组，判断每个num+k是否在map中，在则++ans。最后返回ans。 完整代码如下： [cpp] class Solution { public: int findPairs(vector<int>& nums, int k) { if (k < 0)return 0; int repeated = 0; map<int, int> count; for (const auto& num : nums) { ++count[num]; if (count[num] == 2)++repeated; } if (k == 0)return repeated; vector<int> sorted; for (const auto& it : count) { sorted.push_back(it.first); } int ans = 0; for (const auto& num : sorted) { if (count.find(num + k) != count.end())++ans; } return ans; } }; [/cpp] 本代码提交AC，用时48MS。]]>