[LeetCode] 532 | K-diff Pairs in an Array | Python

---

문제 링크: https://leetcode.com/problems/k-diff-pairs-in-an-array/

---

문제

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.

---

조건

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

---

내 풀이

k가 0일 때, nums에서 중복되는 것을 제거하면 안되기 때문에, k가 0이 아닐 경우에만 nums에서 중복되는 것을 제거한다.

그 후 nums를 정렬한다.

k가 0일 때는, 연속하는 두 수가 같은 지, 그리고 그 수가 이전에 연속하는 수와 같은 지 확인한다.

연속하는 두 수가 같은 지 확인하는 것은 k=0을 만족하는 것을 확인하기 위한 것이고,

그 수가 이전에 연속하는 수와 같은 지 확인하는 것은 nums=[1, 1, 1]일 때 (1, 1)을 중복되게 하지 않기 위해서다.

k가 0이 아닐 때는 이중 for문을 사용하면 된다.

 

이 방법 외에 pair가 unique한 지 매번 저장하면서 확인할 수도 있겠지만, 이번에는 그렇게 풀고싶지 않았다.

---

코드

class Solution:
    def findPairs(self, nums: List[int], k: int) -> int:
        if k > 0:
            nums = list(set(nums))
            
        nums = sorted(nums)
        N = len(nums)
        ans = 0
        
        if k == 0:
            cur = None
            for n in range(N-1):
                if nums[n] == nums[n+1] != cur:
                    ans += 1
                    cur = nums[n]
                    
        else:
            for n in range(N-1):
                for m in range(n+1, N):
                    if nums[m] - nums[n] == k:
                        ans += 1
                    elif nums[m] - nums[n] > k:
                        break
                
        return ans