[leetcode]: 532. K-diff Pairs in an Array

阳光穿透心脏的1/2处 2022-06-14 11:27 81阅读 0赞

# 1.题目 #

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  
> (1, 3) and (3, 5).

虽然数组中有两个1，但只需返回unique pair的个数

> Example 2:  
> Input:\[1, 2, 3, 4, 5\], k = 1  
> Output: 4  
> (1, 2), (2, 3), (3, 4) and (4, 5).

k=0

> Example 3:  
> Input: \[1, 3, 1, 5, 4\], k = 0  
> Output: 1  
> Explanation: There is one 0-diff pair in the array, (1, 1).

k<0

> Example 4:  
> Input:\[1, 2, 3, 4, 5\], k = -1  
> Output: 0  
> 求得是absolute difference

# 2.分析 #

分两种情况：  
k=0, 需要知道有多少种数字是有重复的  
k>0,对与某个元素n，查找n+k是否存在

借助unordered\_map来实现

# 3.代码 #

class Solution {
    public:
        int findPairs(vector<int>& nums, int k) {
            if (nums.size() < 2 || k < 0)
                return 0;
            unordered_map<int, int> hashMap;
            for (int i : nums)
                hashMap[i] += 1;
            int count = 0;
            if (k == 0)//k=0,只需找出有多少重复的元素
            {
                for (unordered_map<int, int>::iterator it = hashMap.begin(); it != hashMap.end(); it++)
                    if (it->second > 1)
                        ++count;
            }
            else {
       //k>0，只需找出比某元素大K的元素是否存在
                for (unordered_map<int, int>::iterator it = hashMap.begin(); it != hashMap.end(); it++)
                    if (hashMap.find(it->first + k) != hashMap.end())
                        ++count;
            }
            return count;
        }
    };