K-diff Pairs in an Array

发表于 | 分类于

K-diff Pairs in an Array

题目描述：

给定一个数组和一个整数k,要求找到数组中|num[i] - num[j]| = k的组合数量。

例子：

具体描述见LeetCode532

解题思路：

本题主要的想法是利用哈希表。我们用哈希表记录下每个数出现的次数；然后遍历哈希表，在遍历到当前数的时候，我们查看哈希表中是否存在key为当前数加上k的数。另外需要判断k为0的情况。

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
public:
    int findPairs(vector<int>& nums, int k) {
        if (k < 0) return 0;
        int res = 0;
        map<int, int> hash;
        for (int i = 0; i < nums.size(); i++){
            hash[nums[i]]++;
        }
        if (k != 0){
            for (auto it = hash.begin(); it != hash.end(); it++){
                if (hash.find(it->first + k) != hash.end())
                    res++;
            }
        }else{
            for (auto it = hash.begin(); it != hash.end(); it++){
                if (it->second > 1)
                    res++;
            }
        }
        return res;
    }
    
};