Medium

题目描述

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

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

  • 0 <= i, j < nums.length
  • i != j
  • |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) 。

提示：

  • 1 <= nums.length <= 10^4
  • -10^7 <= nums[i] <= 10^7
  • 0 <= k <= 10^7

解题思路

这道题要求找出数组中不同的 k-diff 数对数量。关键在于理解题意和避免重复计数。

核心思路分析：

  1. 去重处理：由于要求"不同的"数对，我们需要处理重复元素的影响
  2. 特殊情况：当 k = 0 时，数对要求两个相同的数，此时只需要找出现次数 ≥ 2 的数
  3. 一般情况：当 k > 0 时，对于每个数 x，我们需要查找是否存在 x + k 或 x - k

解法选择：

  1. 哈希表解法（推荐）：使用哈希表统计每个数的出现次数，然后遍历去重后的数字，检查对应的配对数字是否存在
  2. 排序+双指针解法：先排序，然后使用双指针技术查找配对
  3. 集合解法：使用集合去重，然后对每个元素查找配对

推荐使用哈希表解法，因为时间复杂度最优且代码简洁。对于 k = 0 的特殊情况，我们统计出现次数大于1的不同数字个数；对于 k > 0 的情况，我们统计每个数字 x 是否存在 x + k 的配对。

代码实现

class Solution {
public:
    int findPairs(vector<int>& nums, int k) {
        unordered_map<int, int> count;
        for (int num : nums) {
            count[num]++;
        }
        
        int result = 0;
        for (auto& p : count) {
            if (k == 0) {
                if (p.second > 1) {
                    result++;
                }
            } else {
                if (count.count(p.first + k)) {
                    result++;
                }
            }
        }
        
        return result;
    }
};

class Solution:
    def findPairs(self, nums: List[int], k: int) -> int:
        from collections import Counter
        
        count = Counter(nums)
        result = 0
        
        for num in count:
            if k == 0:
                if count[num] > 1:
                    result += 1
            else:
                if num + k in count:
                    result += 1
        
        return result

public class Solution {
    public int FindPairs(int[] nums, int k) {
        var count = new Dictionary<int, int>();
        foreach (int num in nums) {
            if (count.ContainsKey(num)) {
                count[num]++;
            } else {
                count[num] = 1;
            }
        }
        
        int result = 0;
        foreach (var pair in count) {
            if (k == 0) {
                if (pair.Value > 1) {
                    result++;
                }
            } else {
                if (count.ContainsKey(pair.Key + k)) {
                    result++;
                }
            }
        }
        
        return result;
    }
}

/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number}
 */
var findPairs = function(nums, k) {
    const numSet = new Set(nums);
    const seen = new Set();
    let count = 0;
    
    for (const num of numSet) {
        if (k === 0) {
            const occurrences = nums.filter(n => n === num).length;
            if (occurrences > 1) {
                count++;
            }
        } else {
            if (numSet.has(num + k) && !seen.has(num)) {
                count++;
                seen.add(num);
                seen.add(num + k);
            }
        }
    }
    
    return count;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

解法时间复杂度空间复杂度
哈希表解法O(n)O(n)
排序+双指针O(n log n)O(1)

其中 n 为数组长度。哈希表解法是最优解，只需要遍历数组两次，空间换时间获得最佳性能。

相关题目