Easy

题目描述

给你一个整数数组 nums 和一个整数 k，请你返回数对 (i, j) 的数目，满足 i < j 且 |nums[i] - nums[j]| == k。

|x| 的值定义为：

  • 如果 x >= 0 ，那么值为 x
  • 如果 x < 0 ，那么值为 -x

示例 1：

输入：nums = [1,2,2,1], k = 1
输出：4
解释：绝对差值为 1 的数对为：
- |1 - 2| = 1 → (0, 1)
- |1 - 2| = 1 → (0, 2) 
- |2 - 1| = 1 → (1, 3)
- |2 - 1| = 1 → (2, 3)

示例 2：

输入：nums = [1,3], k = 3
输出：0
解释：没有绝对差值为 3 的数对。

示例 3：

输入：nums = [3,2,1,5,4], k = 2
输出：3
解释：绝对差值为 2 的数对为：
- |3 - 1| = 2 → (0, 2)
- |3 - 5| = 2 → (0, 3)  
- |1 - 3| = 2 → (2, 4)

提示：

  • 1 <= nums.length <= 200
  • 1 <= nums[i] <= 100
  • 1 <= k <= 99

解题思路

这道题要求找到所有满足绝对差值为 k 的数对。我们可以考虑两种解法：

方法一：暴力枚举 最直观的解法是使用双重循环遍历所有可能的数对 (i, j)，其中 i < j，然后检查 |nums[i] - nums[j]| 是否等于 k。这种方法简单易懂，代码量少。

方法二：哈希表优化 我们可以使用哈希表来统计每个数字的出现次数。对于每个数字 x，我们需要查找 x + k 和 x - k 在数组中的出现次数。如果 x + k 存在，那么可以形成的数对数量为 count[x] * count[x + k]。注意为了避免重复计算，我们只考虑 x + k 的情况，这样能确保 i < j 的顺序关系。

推荐解法： 考虑到数组长度较小（最多200个元素），两种方法的时间复杂度差异不大，暴力解法更简洁易懂，因此推荐使用暴力解法。

代码实现

class Solution {
public:
    int countKDifference(vector<int>& nums, int k) {
        int count = 0;
        int n = nums.size();
        
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                if (abs(nums[i] - nums[j]) == k) {
                    count++;
                }
            }
        }
        
        return count;
    }
};

class Solution:
    def countKDifference(self, nums: List[int], k: int) -> int:
        count = 0
        n = len(nums)
        
        for i in range(n):
            for j in range(i + 1, n):
                if abs(nums[i] - nums[j]) == k:
                    count += 1
        
        return count

public class Solution {
    public int CountKDifference(int[] nums, int k) {
        int count = 0;
        int n = nums.Length;
        
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                if (Math.Abs(nums[i] - nums[j]) == k) {
                    count++;
                }
            }
        }
        
        return count;
    }
}

/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number}
 */
var countKDifference = function(nums, k) {
    let count = 0;
    for (let i = 0; i < nums.length; i++) {
        for (let j = i + 1; j < nums.length; j++) {
            if (Math.abs(nums[i] - nums[j]) === k) {
                count++;
            }
        }
    }
    return count;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

解法时间复杂度空间复杂度
暴力枚举O(n²)O(1)
哈希表优化O(n)O(n)

相关题目