题目内容:
题目示例:
题目解析:
1 <= nums.length <= 104
-107 <= nums[i] <= 107
0 <= k <= 107
我们拿到本题,读取题意要求在一组整数数组中,求出差值为k的数对对数k-diff。在思考如何解答该题之前,需要明确如下几点细节:
因此,我们的对题目中进行详细了解了,因为会排除重复的数对,我们很容易想哈希表来构建
根据上述思路,我们使用python代码能快速实现,代码如下:
class Solution(object): def findPairs(self, nums, k): """ :type nums: List[int] :type k: int :rtype: int """ ans = set() numset = set() for num in nums: if num - k in numset: ans.add(num-k) if num + k in numset: ans.add(num) numset.add(num) return len(ans)
根据上述思路,使用python代码实现,代码如下:
class Solution(object): def findPairs(self, nums, k): """ :type nums: List[int] :type k: int :rtype: int """ nums.sort() ans = 0 j = 0 for i in range(len(nums)): if i == 0 or nums[i] != nums[i-1]: while j < len(nums) and (nums[j] < nums[i] + k or j <= i): j +=1 if j < len(nums) and nums[j] == nums[i] + k: ans +=1 return ans
本题可以使用哈希方法要使用两个哈希表,属于牺牲空间换取效率。双指针方法,虽然没有用额外的空间,但是速度较于方法一慢一点。
我们用第一种方法,AC提交记录如下: