关于哈希表:数组中的-kdiff-数对

一、题目形容：

题目内容

题目示例

题目解析

1 <= nums.length <= 104
-107 <= nums[i] <= 107
0 <= k <= 107

二、思路剖析：
咱们拿到本题，读取题意要求在一组整数数组中，求出差值为 k 的数对对数 k -diff。在思考如何解答该题之前，须要明确如下几点细节：

nums 数组元素都是整数
索引地位 i 与地位 j, 不能相等
k-diff 数对关系：nums[i] – nums[j] = k -> nums[i] = nums[j] + k -〉 nums[i] – k = nums[j]
k-diff 数对，存在雷同数对状况，但后果只取 1 次

因而，咱们的对题目中进行具体理解了，因为会排除反复的数对，咱们很容易想哈希表来构建

办法一：构建哈希表

数对中反复场景如示例一中差值为 k =1,(1,3) & (3,1)视为一种状况，则要定义两个哈希表来贮存
哈希表能够通过字典 k -value 或者汇合 set(), 本题无需思考索引关系定义 ans,numset 两个汇合
当 nums[i] > nums[j], 则 nums[j] = nums[i] – k 在 numset 中，取最小的那一个则 ans.add(nums[i]-k),
当 nuns[i] < nums[j], 则 nums[j] = nums[i] + k 在 numset 中，取较小的那一个则 ans.add(nums[i])

根据上述思路，咱们应用 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)

复制代码

办法二：双指针

首先对 nums 数组中的元素依照从低到高的顺序排列
在递增的数组中，因为双指针 i!=j，因而 i 指针肯定是小于 j 的
枚举查找的判断的条件 nums[j] < nums[i]+k, 指针 j 则往后挪动
当 nums[j] = nums[i] + k 时，则对数次数 +1

根据上述思路，应用 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