532. K-diff Pairs in an Array

朴灿烈づ我的快乐病毒、 2022-06-03 04:17 100阅读 0赞

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的数，如果存在就是将有差值的一对数将其中的较小值放入到哈希表中，这样就避免了重复的一对数的出现，这种思路不太容易想到，但是也是时间复杂度也是比较小的，只需要将数组循环一遍。

![这里写图片描述][SouthEast]

--------------------

//
    // 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;
    }

[SouthEast]: /images/20220603/287c6a6b1e4c40159172f3724c48d1e5.png