Description:
Given an array of integers and an integer k, you need to find the number of unique k-diff pairs in the array. Here ak-diffpair is defined as an integer pair (i, j), where i and j are both numbers in the array and theirabsolute 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].
思路:题目意思是给出一组数组,要求查找绝对值差值为 k 的组合有多少个,可以使用 unordered_map 映射,直接查找某个值-k 是否存在,value 存储数组的值出现的次数,因为当 k=0 的时候,需要判断是否该值是否有不少于出现两次,除此之外我们就只用判断 k 值是否存在即可。特别注意 unordered_map 中 count 方法,只返回 1(存在)或 0(不存在)。
C++ 代码
class Solution {
public:
int findPairs(vector<int>& nums, int k) {
if (k < 0)
return 0;
unordered_map<int, int> umap;
for (int num : nums)
umap[num]++;
int count = 0;
for (auto u : umap){
if (k == 0){
if (u.second >=2 )
count++;
}
else{
count += umap.count(u.first - k);
}
}
return count;
}
};
运行时间:42ms
运行内存:12.5M
欢迎来到这里!
我们正在构建一个小众社区,大家在这里相互信任,以平等 • 自由 • 奔放的价值观进行分享交流。最终,希望大家能够找到与自己志同道合的伙伴,共同成长。
注册 关于