## 题目描述 给你一个整数数组 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 **暴力，二重循环** 判断每对（i, j）之间的绝对值是否为k ```java public int countKDifference(int[] nums, int k) { int res = 0; for(int i=0;i<nums.length;i++){ for(int j=i+1;j<nums.length;j++){ if(Math.abs(nums[i]-nums[j])==k) res++; } } return res; } ``` **复杂度** 时间复杂度：二重循环遍历 $$O(N^2)$$ 空间复杂度：记录最终结果res $$O(1)$$ #### 思路2 **Hash表记录** 通过hashmap记录每个数字出现的次数<数字，次数>，当添加一个数字i的时候，寻找之前的hashmap的key里面是否有i+k或者i-k,查看其出现的此处。通过这种方式，以$$O(N)$$复杂度达到二重循环遍历的效果。 **复杂度** 时间复杂度：一次循环遍历 $$O(N)$$ 空间复杂度：HashMap记录 $$O(N)$$ ```java public int countKDifference(int[] nums, int k) { int res = 0; HashMap<Integer, Integer> map = new HashMap<>(); for(int i: nums){ res += map.getOrDefault(i+k, 0); res += map.getOrDefault(i-k, 0); map.put(i, map.getOrDefault(i, 0)+1); } return res; } ``` 最后编辑：2024年04月23日 ©著作权归作者所有 赞 0 分享
最新回复