0532._K-diff_Pairs_in_an_Array.md

532. K-diff Pairs in an Array

难度: Easy

刷题内容

原题连接

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

内容描述

Given an array of integers and an integer k, you need to find the number of unique k-diff pairs in the array. Here a k-diff pair is defined as an integer pair (i, j), where i and j are both numbers in the array and their absolute difference is k.

Example 1:
Input: [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:[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: [1, 3, 1, 5, 4], k = 0
Output: 1
Explanation: There is one 0-diff pair in the array, (1, 1).
Note:
The pairs (i, j) and (j, i) count as the same pair.
The length of the array won't exceed 10,000.
All the integers in the given input belong to the range: [-1e7, 1e7].

解题方案

思路 1 - 时间复杂度: O(NlgN)- 空间复杂度: O(N)******

首先如果k小于0肯定返回0，因为题目说的是 absolute difference is k.

然后我们用一个字典存下数字和其出现频率，要注意一下我们当k=0的时候我们要确保这个数字出现的频率是要大于等于2的，否则是取不到的

beats 69.83%

class Solution(object):
    def findPairs(self, nums, k):
        """
        :type nums: List[int]
        :type k: int
        :rtype: int
        """
        if k < 0:
            return 0
        lookup = collections.Counter(nums)
        res = 0
        for num in sorted(list(set(nums))):
            if num + k in lookup:
                if (k == 0 and lookup[num] >= 2) or k != 0:
                    res += 1
        return res

思路 2 - 时间复杂度: O(N)- 空间复杂度: O(N)******

后面我发现，完全不需要排序，我只要确保k是大于0的和等于0的区分开来就行了

beats 82.42%

class Solution(object):
    def findPairs(self, nums, k):
        """
        :type nums: List[int]
        :type k: int
        :rtype: int
        """
        if k < 0:
            return 0
        lookup = collections.Counter(nums)
        res = 0
        for num in lookup:
            if num + k in lookup:
                if (k == 0 and lookup[num] >= 2) or k != 0:
                    res += 1
        return res

两行版本

class Solution(object):
    def findPairs(self, nums, k):
        """
        :type nums: List[int]
        :type k: int
        :rtype: int
        """
        lookup = collections.Counter(nums)
        return  sum((k > 0 and num + k in lookup) or (k == 0 and lookup[num] >= 2) for num in lookup)