目录

题目描述

思路分析

我的题解

题目描述

给你一个整数数组 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,2,1]
        - [1,2,2,1]
        - [1,2,2,1]
        - [1,2,2,1]

示例 2：

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

示例 3：

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

 

提示：

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

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/count-number-of-pairs-with-absolute-difference-k
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路分析

        看到题目很容易想到的就是用两层for循环的暴力求解法，其时间复杂度为O(N²)，显然这并不是我们想要的解法。

       我们设nums[i]为X，nums[j]为Y，那么 |X-Y|=k，则 X=Y+k / X=Y-k ，即满足X等于Y加减k所对应的下标i、j就是符合题目条件的。我们以j为游标对nums进行一次遍历，即遍历过程中的当前元素为Y，这里我们还需要定义一个哈希表count用于存放与Y所对应的X个数。由于题目是统计符合条件的对数，所以对于|X-Y|=k我们只需要统计满足条件的与每个Y所对应的X个数，即对于遍历过程中的每个Y，我们只需要统计与之对应的X的个数。

例如，设有下方这样一个nums数组，其中X与Y表示符合条件的数，O表示其他的数。我们设统计的符合条件数为ans对。

XXXXYXYOO

这个数组有2个Y和5个X，期中一个X被夹在两个Y之间。对于第一个Y，此前有4个与之对应的X，那么就将ans加4。对于被夹在Y之间的X，在它之前有一个与之对应的Y，那么再将ans加1。对于第二个Y，前面有5个与之对应的X，那么我们再将ans加5。最后得到我们的ans即符合条件的数共有1+4+5=10对。具体的代码实现见“我的题解”部分。 
 

我的题解

题解与思路分析部分有些命名的出入，比如思路部分的Y在代码中写的是t。

class Solution {
public:int countKDifference(vector<int>& nums, int k) {//思路：哈希表unordered_map<int,int> count; //数字 - 对应数字的数量int ans = 0;//利用对称性，可以边遍历边记录for(auto t : nums){//存在t+k和t-k都有的情况，所以不能用 if - else if if(count.find(t + k) != count.end())ans += count[t + k];if(count.find(t - k) != count.end())ans += count[t - k];count[t]++;}return ans;}
};