532 数组中的 k-diff 数对（枚举、双指针）

Bertha 。 2022-08-30 15:42 138阅读 0赞

**1. 问题描述：**

给定一个整数数组和一个整数 k，你需要在数组里找到不同的 k-diff 数对，并返回不同的 k-diff 数对的数目。这里将 k-diff 数对定义为一个整数对 (nums\[i\], nums\[j\])，并满足下述全部条件：  
0 <= i < j < nums.length  
|nums\[i\] - nums\[j\]| == k  
注意，|val| 表示 val 的绝对值。

**示例 1：**

输入：nums = \[3, 1, 4, 1, 5\], k = 2  
输出：2  
解释：数组中有两个 2-diff 数对, (1, 3) 和 (3, 5)。  
尽管数组中有两个1，但我们只应返回不同的数对的数量。

**示例 2：**

输入：nums = \[1, 2, 3, 4, 5\], k = 1  
输出：4  
解释：数组中有四个 1-diff 数对, (1, 2), (2, 3), (3, 4) 和 (4, 5)。

**示例 3：**

输入：nums = \[1, 3, 1, 5, 4\], k = 0  
输出：1  
解释：数组中只有一个 0-diff 数对，(1, 1)。

**示例 4：**

输入：nums = \[1,2,4,4,3,3,0,9,2,3\], k = 3  
输出：2

**示例 5：**

输入：nums = \[-1,-2,-3\], k = 1  
输出：2  
提示：  
1 <= nums.length <= 10 ^ 4  
\-10 ^ 7 <= nums\[i\] <= 10 ^ 7  
0 <= k <= 10 ^ 7  
来源：力扣（LeetCode）  
链接：https://leetcode-cn.com/problems/k-diff-pairs-in-an-array

**2. 思路分析：**

分析题目可以知道diff数对与数字的顺序是无关的，所以为了后面方便处理可以先排个序（这是一个处理不考虑顺序的技巧，当数组有序之后那么就可以考虑使用二分/双指针这些算法），我们先考虑如何枚举才可以将所有答案枚举出来，一般枚举的是以当前的位置i为终点的时候之前...的（**枚举i为终点是常见的枚举技巧**），这里也是可以考虑枚举当前以i为终点，找到每一个以i结尾的diff数对那么就可以将所有答案枚举出来，对于每一个位置i我们需要找到在i之前第一个满足条件的j，使得ai - aj = k，可以发现对于每一个ai如果如果满足ai - aj = k那么aj一定是唯一的（枚举i的时候那么表示枚举的是较大的那个数字)。对于当前的ai找到第一个满足条件的aj可以使用**双指针算法**，因为当指针i往后走到 i' 的时候，如果指针j往前走到了 j'，说明\[j'，i'\]是小于等于k的，所以\[j'， i\]也是小于等于k的，说明在i这个位置第一个满足条件的为j'而不是j与第一个位置再j就矛盾了，所以i往后走的时候j一定是往后的，也即两个指针是单调的那么就可以使用双指针算法了。并且答案中可能存在连续一段的重复数字，对于重复的数字只算其中一种情况，所以对于连续的重复数字我们只需要计算其中一个数字即可，这里计算的是哪一个呢？考虑到k = 0的情况如果计算的是第一个数字的话那么可能当前这一段重复数字的方案就没有计算在答案之内了，所以我们可以考虑计算当前这一段最后一个重复的数字。

**3. 代码如下：**

from typing import List
    
    
    class Solution:
        def findPairs(self, nums: List[int], k: int) -> int:
            # 因为不考虑diff数对的顺序所以我们可以先对数组排序
            nums.sort()
            i, j = 0, 0
            n = len(nums)
            res = 0
            while i < n:
                # 因为可能存在多个重复的数字而且k可能等于0所以我们考虑使用最后一个重复数字
                # 这样k = 0的情况也可以处理
                while i + 1 < n and nums[i] == nums[i + 1]: i += 1
                # 双指针算法找到第一个小于等于k的aj
                while j < n and nums[i] - nums[j] > k: j += 1
                # 判断是否满足条件
                if j < i and nums[i] - nums[j] == k: res += 1
                i += 1
            return res