532. K-diff Pairs in an Array
程序员文章站
2022-03-07 18:40:55
...
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 :
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.
这道题我最开始的思路是将有差值的一对数放入到哈希表中,然后讲以后有差值的数在哈希表中进行比对,是key和value都进行比对,但是有错误,我也不知道哪里错误了,代码贴了出来,有谁知道了可以告诉我一下。
在最优解中,在查找中,在之前放入到indices哈希表中进行查找nums[i]+k || nums[i]-k的数,如果存在就是将有差值的一对数将其中的较小值放入到哈希表中,这样就避免了重复的一对数的出现,这种思路不太容易想到,但是也是时间复杂度也是比较小的,只需要将数组循环一遍。
//
// Created by will on 2017/12/18.
//
#include <iostream>
#include <vector>
#include <unordered_map>
#include <map>
#include <unordered_set>
using namespace std;
class Solution{
public:
int findPairs(vector<int>& nums, int k){
/*
map<int,int> map;
int number = 0;
for (int i = 0; i < nums.size(); ++i) {
for (int j = i+1; j < nums.size(); ++j) {
if (abs(nums[i] - nums[j]) == k){
cout<<"k = "<<k<<" i and j :"<<nums[i]<<" . "<<nums[j]<<endl;
if(judgment(map, nums[i], nums[j])){
map.insert(pair<int, int>(nums[i],nums[j]));
number++;
}
}
}
}
return number;
*/
if (k < 0) {
return 0;
}
unordered_set<int> starters;
unordered_map<int, int> indices;
for (int i = 0; i < nums.size(); i++) {
if (indices.count(nums[i] - k)) {
starters.insert(nums[i] - k);
}
if (indices.count(nums[i] + k)) {
starters.insert(nums[i]);
}
indices[nums[i]] += 1;
}
return starters.size();
}
bool judgment(map<int,int>& map, int i, int j){
if(map.count(i) && map[i] == j){
return false;
}
else if (map.count(j) && map[j] == i){
return false;
}else{
cout<<"inputnumbers:"<<i<<" "<<j<<endl;
return true;
}
}
};
int main(){
vector<int> nums = {6,2,9,3,9,6,7,7,6,4};
Solution s;
int num = s.findPairs(nums, 3);
cout<<"the num is :"<<num;
return 0;
}