leetcode 532) K-diff Pairs in an Array

LV. Medium 🧐

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

K-diff Pairs in an Array - LeetCode

 

문제

Given an array of integers nums and an integer k, return the number of unique k-diff pairs in the array.

A k-diff pair is an integer pair (nums[i], nums[j]), where the following are true:

• 0 <= i < j < nums.length
• |nums[i] - nums[j]| == k

Notice that |val| denotes the absolute value of val.

 

Example 1:

Input: nums = [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.

Example 2:

Input: nums = [1,2,3,4,5], k = 1
Output: 4
Explanation: There are four 1-diff pairs in the array, (1, 2), (2, 3), (3, 4) and (4, 5).

Example 3:

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

 

Constraints:

• 1 <= nums.length <= 10^4
• -10^7 <= nums[i] <= 10^7
• 0 <= k <= 10^7

 

문제 해결법

공통의 쌍이 들어가지 못하도록 만들어진 쌍은 map에 저장해줬다.

k + i인 값, i - k인 값 두 가지가 nums에 있나 확인하면서 배열을 한 번 돌아줬다.

 

해결 코드

class Solution {
private:
	int _k;

public:
	int findPairs(vector<int>& nums, int k) {
		int size = nums.size();
		_k = k;
		unordered_map<int, vector<int>> m;
		unordered_map<int, int> ans;

		for (int i = 0; i < size; ++i) {
			m[nums[i]].push_back(i);
		}
		for (int i = 0; i < size; ++i) {
			int *list = new int[2];
			set_num(list, nums[i]);

			for (int j = 0; j < 2; ++j) {
				auto it = m.find(list[j]);
				if (it != m.end()) {
					for (int idx : it->second) {
						if (idx != i) {
							ans[max(list[j], nums[i])] = min(list[j], nums[i]);
							break;
						}
					}
				}
				m.erase(nums[i]);
			}
		}
		return ans.size();
	}

	void set_num(int *(&list), int num) {
		list[0] = _k + num;
		list[1] = num - _k;
	}
};