各地残疾人联合会网站建设,网站建设与推广是什么,国家重大建设项目库网站,沈阳红方城网站建设文章目录题目标题和出处难度题目描述要求示例数据范围解法思路和算法代码复杂度分析题目
标题和出处
标题#xff1a;数组中的 k-diff 数对
出处#xff1a;532. 数组中的 k-diff 数对
难度
4 级
题目描述
要求
给定一个整数数组 nums\texttt{nums}nums 和一个整数 k…
文章目录题目标题和出处难度题目描述要求示例数据范围解法思路和算法代码复杂度分析题目
标题和出处
标题数组中的 k-diff 数对
出处532. 数组中的 k-diff 数对
难度
4 级
题目描述
要求
给定一个整数数组 nums\texttt{nums}nums 和一个整数 k\texttt{k}k返回不同的 k\texttt{k}k-diff 数对的数目。
一个 k\texttt{k}k-diff 数对为一个整数对 (nums[i],nums[j])\texttt{(nums[i], nums[j])}(nums[i], nums[j])并满足下述条件
0≤i,jnums.length\texttt{0} \le \texttt{i, j} \texttt{nums.length}0≤i, jnums.lengthnums[i]≤nums[j]\texttt{nums[i]} \le \texttt{nums[j]}nums[i]≤nums[j]|nums[i]-nums[j]|k\texttt{|nums[i] - nums[j]|} \texttt{k}|nums[i] - nums[j]|k
注意|val|\texttt{|val|}|val| 表示 val\texttt{val}val 的绝对值。
示例
示例 1
输入nums[3,1,4,1,5],k2\texttt{nums [3, 1, 4, 1, 5], k 2}nums [3, 1, 4, 1, 5], k 2 输出2\texttt{2}2 解释数组中有两个 2\texttt{2}2-diff 数对(1,3)\texttt{(1, 3)}(1, 3) 和 (3,5)\texttt{(3, 5)}(3, 5)。 尽管数组中有两个 1\texttt{1}1但我们只应返回不同的数对的数量。
示例 2
输入nums[1,2,3,4,5],k1\texttt{nums [1, 2, 3, 4, 5], k 1}nums [1, 2, 3, 4, 5], k 1 输出4\texttt{4}4 解释数组中有四个 1\texttt{1}1-diff 数对(1,2)\texttt{(1, 2)}(1, 2)(2,3)\texttt{(2, 3)}(2, 3)(3,4)\texttt{(3, 4)}(3, 4) 和 (4,5)\texttt{(4, 5)}(4, 5)。
示例 3
输入nums[1,3,1,5,4],k0\texttt{nums [1, 3, 1, 5, 4], k 0}nums [1, 3, 1, 5, 4], k 0 输出1\texttt{1}1 解释数组中只有一个 0\texttt{0}0-diff 数对(1,1)\texttt{(1, 1)}(1, 1)。
数据范围
1≤nums.length≤104\texttt{1} \le \texttt{nums.length} \le \texttt{10}^\texttt{4}1≤nums.length≤104-107≤nums[i]≤107\texttt{-10}^\texttt{7} \le \texttt{nums[i]} \le \texttt{10}^\texttt{7}-107≤nums[i]≤1070≤k≤107\texttt{0} \le \texttt{k} \le \texttt{10}^\texttt{7}0≤k≤107
解法
思路和算法
由于题目要求计算数组 nums\textit{nums}nums 中的不同的差为 kkk 的数对的数目因此只需要考虑数组中有哪些数字不需要考虑顺序。
计算差为 kkk 的数对的数目需要考虑两种情况分别是 k0k 0k0 和 k0k 0k0。
当 k0k 0k0 时每个差为 kkk 的数对由两个相等的整数组成对于任意整数 num\textit{num}num只有当 num\textit{num}num 在数组 nums\textit{nums}nums 中出现次数大于 111 次时才有数对 (num,num)(\textit{num}, \textit{num})(num,num)。遍历数组 nums\textit{nums}nums 并用哈希表记录每个数字的出现次数然后遍历哈希表对于哈希表中的每个数字如果出现次数大于 111 次则将数对的数目加 111。遍历哈希表结束之后即可得到差为 kkk 的数对的数目。
当 k0k 0k0 时每个差为 kkk 的数对由两个不相等的整数组成对于任意整数 num\textit{num}num当 num\textit{num}num 和 numk\textit{num} knumk 都在数组中出现时有数对 (num,numk)(\textit{num}, \textit{num} k)(num,numk)。遍历数组 nums\textit{nums}nums 并用哈希集合记录出现的数字然后遍历哈希集合对于哈希集合中的每个数字 num\textit{num}num如果 numk\textit{num} knumk 也在哈希集合中则将数对的数目加 111。遍历哈希集合结束之后即可得到差为 kkk 的数对的数目。
代码
class Solution {public int findPairs(int[] nums, int k) {int pairs 0;if (k 0) {MapInteger, Integer map new HashMapInteger, Integer();for (int num : nums) {map.put(num, map.getOrDefault(num, 0) 1);}SetInteger set map.keySet();for (int num : set) {if (map.get(num) 1) {pairs;}}} else {SetInteger set new HashSetInteger();for (int num : nums) {set.add(num);}for (int num : set) {if (set.contains(num k)) {pairs;}}}return pairs;}
}复杂度分析 时间复杂度O(n)O(n)O(n)其中 nnn 是数组 nums\textit{nums}nums 的长度。需要遍历数组一次使用哈希表或哈希集合存储数组中的不同数字然后遍历哈希表或哈希集合一次由于哈希表或哈希集合中的元素个数不超过数组长度因此时间复杂度是 O(n)O(n)O(n)。 空间复杂度O(n)O(n)O(n)其中 nnn 是数组 nums\textit{nums}nums 的长度。需要使用哈希表或哈希集合存储数组中的不同数字最坏情况下需要存储数组中的全部数字。
