LeetCode 풀이 - 2006. Count Number of Pairs With Absolute Difference K

2006. Count Number of Pairs With Absolute Difference K

문제)

 

솔루션1)

• Brute-force

class Solution:
    def countKDifference(self, nums: List[int], k: int) -> int:
        count = 0
        for i in range(len(nums)):
            for j in range(i, len(nums)):
                if i != j and abs(nums[i] - nums[j]) == k:
                    count += 1
        return count

솔루션2)

• 조합 사용

class Solution:
    def countKDifference(self, nums: List[int], k: int) -> int:
        count = 0
        for i, j in combinations(nums, 2):
            if abs(i-j) == k:
                count += 1
        return count

솔루션3)

• dict를 이용한 O(n)

class Solution:
    def countKDifference(self, nums: List[int], k: int) -> int:
        seen = defaultdict(int)
        count = 0
        for num in nums:
            count += seen[num - k] + seen[num + k]
            seen[num] += 1
        return count