- 每日一题：LeetCode：2006.差的绝对值为K的数对
- 时间：2022-02-09
- 力扣难度：Easy
- 个人难度：Easy
- 数据结构：哈希表
2022-02-09：LeetCode：2006.差的绝对值为K的数对
1. 题目描述
题目：原题链接
- 给你一个整数数组 nums 和一个整数 k ，请你返回数对 (i, j) 的数目，满足 i < j 且 |nums[i] - nums[j]| == k 。
- |x| 的值定义为：
- 如果 x >= 0 ，那么值为 x 。
- 如果 x < 0 ，那么值为 -x 。
输入输出规范
- 输入：数组nums，差值k
- 输出：数对个数
输入输出示例
- 输入：nums = [1,2,2,1], k = 1
- 输出：4
2. 方法一：贪心 & 排序 & 二维数组
思路
- 本题类似两数之和，区别就是本题是两数的差的绝对值为一个常数
- 暴力解法是两重循环，可以通过哈希表优化到线性，一次遍历中解决
题解
1
2
3
4
5
6
7
8
9
10
11public int countKDifference(int[] nums, int k) {
if(nums == null || nums.length == 0) return 0;
Map<Integer, Integer> map = new HashMap<>();
int count = 0;
for(int num : nums){
if(map.containsKey(num + k)) count += map.get(num + k);
if(map.containsKey(num - k)) count += map.get(num - k);
map.put(num, map.getOrDefault(num, 0) + 1);
}
return count;
}复杂度分析：n 是数组的大小
- 时间复杂度：$O(n)$
- 空间复杂度：$O(n)$
本文作者：
Chthollists
发布时间： 2022-02-09 16:33:20
最后更新： 2022-02-20 13:34:08
本文标题： 每日一题:LeetCode:2006.差的绝对值为K的数对
本文链接： https://chthollists.github.io/post/7a3b2879.html
版权声明： 本作品采用 CC BY-NC-SA 4.0 许可协议进行许可。转载请注明作者和出处！
发布时间： 2022-02-09 16:33:20
最后更新： 2022-02-20 13:34:08
本文标题： 每日一题:LeetCode:2006.差的绝对值为K的数对
本文链接： https://chthollists.github.io/post/7a3b2879.html
版权声明： 本作品采用 CC BY-NC-SA 4.0 许可协议进行许可。转载请注明作者和出处！
