首页 > 代码库 > 532. K-diff Pairs in an Array

532. K-diff Pairs in an Array

2024-09-28 08:47:39   215人阅读

https://leetcode.com/problems/k-diff-pairs-in-an-array/#/description

This is a very simple question. With two-pointer method, the time complexity is O(nlogn), because you need to sort it first. With a hashmap, you could save the time to rearrange it and hence it is only O(n). 

The key points of the question are the boundary conditions. I forgot to consider the cases where k = 0 and k < 0!

Codes with a hashmap:

class Solution {
public:
    int findPairs(vector<int>& nums, int k) {
        if (nums.empty() || k < 0) return 0;
        int result = 0;
        unordered_map<int, int> set;
        for (int i: nums) {
            set[i]++;
        }
        if (k == 0) {
            for (auto i: set) {
                if (i.second > 1) result++;
            }
        }
        else {
            for (auto i: set) {
                if (set.count(i.first + k)) result++;
            }
        }
        return result;
    }
};

 

532. K-diff Pairs in an Array


联系
我们