K-diff Pairs in an Array

Posted on | Edited on | In | | Views:

532. K-diff Pairs in an Array

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.

给一个数组, 返回所有的k-diff组合.

例子:

[3, 1, 4, 1, 5], k = 2
=> 2

k-diff组合为(1, 3), (5, 3)

[1, 2, 3, 4, 5], k = 1

k-diff组合为(1, 2), (2, 3), (3, 4), (4, 5)

思路

排序后从左往右扫描数组, 只看右边能组成k-diff的数字.

Code

1
2
3
4
5
6
7
8
9
10
11
12
def kDiff(nums, k):
    nums.sort()
    res = set()
    for i in range(len(nums)):
        j = i + 1
        while j < len(nums):
            if abs(nums[j] - nums[i]) > k:
                break
            if abs(nums[j] - nums[i]) == k:
                res.add((nums[i], nums[j]))
            j += 1
    return len(res)

##时间复杂度
$O(nlogn) + O(n)$

EOF