[LeetCode] 532. K-diff Pairs in an Array

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

K-diff Pairs in an Array - LeetCode

K-diff Pairs in an Array - Medium

 

array nums내의 두 수의 차의 절대값이 k가 되는 중복되지 않는 쌍이 몇개가 존재하는지 구하는 문제다.

map m을 하나 만들어 nums 의 num을 훑으며 num을 저장해준다.

m에 만약 num-k가 있다면, (num-k, num) 쌍이 존재하는 것인데, 더 작은 수인 num-k를 set s를 만들어 추가해준다.

num+k가 있다면 (num, num+k) 쌍이 존재하므로, 더 작은 수인 num을 s에 추가해준다.

마지막으로 s의 size()를 리턴해준다.

 

class Solution {
public:
    int findPairs(vector<int>& nums, int k) {
        unordered_set<int> s;
        unordered_map<int, int> m;
        for (int num:nums) {
            if (m[num-k]==1 && s.find(num-k)==s.end()) s.insert(num-k);
            if (m[num+k]==1 && s.find(num)==s.end()) s.insert(num);
            m[num]=1;
        }
        return s.size();
    }
};