题目描述
给定一个整数数组和一个整数 k, 你需要在数组里找到不同的 k-diff 数对。这里将 k-diff 数对定义为一个整数对 (i, j), 其中 i 和 j 都是数组中的数字,且两数之差的绝对值是 k.
示例 1:
输入: [3, 1, 4, 1, 5], k = 2 输出: 2 解释: 数组中有两个 2-diff 数对, (1, 3) 和 (3, 5)。 尽管数组中有两个1,但我们只应返回不同的数对的数量。
示例 2:
输入:[1, 2, 3, 4, 5], k = 1 输出: 4 解释: 数组中有四个 1-diff 数对, (1, 2), (2, 3), (3, 4) 和 (4, 5)。
示例 3:
输入: [1, 3, 1, 5, 4], k = 0 输出: 1 解释: 数组中只有一个 0-diff 数对,(1, 1)。
注意:
解法
根据题意可知,对于一个元素 v_i
,若数组中存在另一个元素 v_j
,使得|v_i-v_j|=k
,则 (v_i, v_j)
构成一个 k-diff
数对。
不妨遍历数组,以 s
作为已遍历的元素集合,对于每个元素,判断集合中否存在另一个元素匹配以构成 k-diff
数对。
不妨只存储
k-diff
数对中较小或较大对元素,以减少空间开销
class Solution:
def findPairs(self, nums: List[int], k: int) -> int:
if k<0:
return 0
s=set()
ret=set()
for c in nums:
if c-k in s:
ret.add(c-k)
if c+k in s:
ret.add(c)
s.add(c)
return len(ret)