1.题目基本信息

1.1.题目描述

给你一个整数数组 nums 和一个整数 k，请你在数组中找出 不同的 k-diff 数对，并返回不同的 k-diff 数对 的数目。

k-diff 数对定义为一个整数对 (nums[i], nums[j]) ，并满足下述全部条件：

• 0 <= i, j < nums.length

• i != j

• |nums[i] - nums[j]| == k

注意，|val| 表示 val 的绝对值。

1.2.题目地址

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

2.解题方法

2.1.解题思路

哈希表 / 排序+双指针

2.2.解题步骤

排序+双指针步骤：

第一步，构建维护变量。指针i指向nums连续子数组的首部位置；指针j指向i后面第一个大于等于nums[i]的位置

第二步，遍历

• 2.1.根据维护的性质，更新指针j

• 2.2.更新结果变量

• 2.3.根据维护性质，更新指针i

3.解题代码

python3代码-哈希表

class Solution:
    def findPairs(self, nums: List[int], k: int) -> int:
        # 思路1：哈希表
        visited = set()
        result = set()
        for num in nums:
            # 数对没有顺序要求，统一存数对中小的元素
            if num - k in visited:
                result.add(num - k)
            if num + k in visited:
                result.add(num)
            visited.add(num)
        return len(result)

python3代码-排序+双指针

class Solution:
    def findPairs(self, nums: List[int], k: int) -> int:
        # 思路2：排序+双指针
        n = len(nums)
        nums.sort()
        # print(nums)
        # 第一步，构建维护变量。指针i指向nums连续子数组的首部位置；指针j指向i后面第一个大于等于nums[i]的位置
        i, j = 0, 0
        result = 0
        # 第二步，遍历
        while i < n:
            # 2.1.根据维护的性质，更新指针j
            while j <= i or (j < n and nums[j] < nums[i] + k):
                j += 1
            # 2.2.更新结果变量
            if j < n and nums[j] == nums[i] + k:
                result += 1
            # 2.3.根据维护性质，更新指针i
            i += 1
            while i == 0 or (i < n and nums[i] == nums[i - 1]):
                i += 1
        return result

4.执行结果