描述
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:
The pairs (i, j) and (j, i) count as the same pair.The length of the array won't exceed 10,000.
All the integers in the given input belong to the range: [-1e7, 1e7].
分析
一开始我是想用两个for循环做的，后来发现漏了各种边界情况，提交数次都无法ac，深感无力。后来0看了讨论区（https://discuss.leetcode.com/topic/81702/o-n-concise-solution-c ）的解法恍然大悟：用一个unordered_map即可解决！
用unordered_map<int,int>，key 值保存数组元素，value保存该元素个数。
因此只需遍历这个map，判断这个map里是否存在键值加上k后的键值即可。
唯一需要考虑的是k=0的情况，因为k=0时只有两个相等的元素才能满足。并且根据题意，即使有n对匹配元素(val1,val2)是k匹配的，也只算做一对。因此k=0时，只需要判断这个元素的个数即可，有两个及以上便将个数加1.
代码如下：
class Solution {
public:
int findPairs(vector<int>& nums, int k) {
if(k < 0)return 0;
int k_diff = 0;
unordered_map<int,int>um;
for(int i = 0; i != nums.size(); ++i)
++um[nums[i]];
if(k != 0){
for(auto it = um.begin(); it != um.end(); ++it)
if(um.find(it->first + k) != um.end())
++k_diff;
}else{
for(auto it = um.begin(); it != um.end(); ++it)
if(it->second > 1)
++k_diff;
}
return k_diff;
}
};
心得
写个心得。
unordered_map真心好用啊，很多操作的复杂度也低，在大多数情况下简直是上上之选，以后解题的时候可以优先考虑用unordered_map！