題目

標(biāo)題和出處

標(biāo)題：數(shù)組中的 k-diff 數(shù)對

出處：532. 數(shù)組中的 k-diff 數(shù)對

難度

4 級

題目描述

要求

給定一個整數(shù)數(shù)組 $\text{nums}$ 和一個整數(shù) $\text{k}$，返回不同的 $\text{k}$-diff 數(shù)對的數(shù)目。

一個 $\text{k}$-diff 數(shù)對為一個整數(shù)對 $\text{(nums[i],?nums[j])}$，并滿足下述條件：

• $\text{0}\le \text{i,?j}<\text{nums.length}$
• $\text{nums[i]}\le \text{nums[j]}$
• $\text{|nums[i]?-?nums[j]|}=\text{k}$

注意，$\text{|val|}$ 表示 $\text{val}$ 的絕對值。

示例

示例 1：

輸入：$\text{nums?=?[3,?1,?4,?1,?5],?k?=?2}$
輸出：$\text{2}$
解釋：數(shù)組中有兩個 $\text{2}$-diff 數(shù)對，$\text{(1,?3)}$ 和 $\text{(3,?5)}$。
盡管數(shù)組中有兩個 $\text{1}$，但我們只應(yīng)返回不同的數(shù)對的數(shù)量。

示例 2：

輸入：$\text{nums?=?[1,?2,?3,?4,?5],?k?=?1}$
輸出：$\text{4}$
解釋：數(shù)組中有四個 $\text{1}$-diff 數(shù)對，$\text{(1,?2)}$，$\text{(2,?3)}$，$\text{(3,?4)}$ 和 $\text{(4,?5)}$。

示例 3：

輸入：$\text{nums?=?[1,?3,?1,?5,?4],?k?=?0}$
輸出：$\text{1}$
解釋：數(shù)組中只有一個 $\text{0}$-diff 數(shù)對，$\text{(1,?1)}$。

數(shù)據(jù)范圍

• $\text{1}\le \text{nums.length}\le {\text{10}}^{\text{4}}$
• ${\text{-10}}^{\text{7}}\le \text{nums[i]}\le {\text{10}}^{\text{7}}$
• $\text{0}\le \text{k}\le {\text{10}}^{\text{7}}$

解法

思路和算法

由于題目要求計算數(shù)組 $\text{nums}$ 中的不同的差為 $k$ 的數(shù)對的數(shù)目，因此只需要考慮數(shù)組中有哪些數(shù)字，不需要考慮順序。

計算差為 $k$ 的數(shù)對的數(shù)目需要考慮兩種情況，分別是 $k=0$ 和 $k>0$。

當(dāng) $k=0$ 時，每個差為 $k$ 的數(shù)對由兩個相等的整數(shù)組成，對于任意整數(shù) $\text{num}$，只有當(dāng) $\text{num}$ 在數(shù)組 $\text{nums}$ 中出現(xiàn)次數(shù)大于 $1$ 次時，才有數(shù)對 $(\text{num},\text{num})$。遍歷數(shù)組 $\text{nums}$ 并用哈希表記錄每個數(shù)字的出現(xiàn)次數(shù)，然后遍歷哈希表，對于哈希表中的每個數(shù)字，如果出現(xiàn)次數(shù)大于 $1$ 次，則將數(shù)對的數(shù)目加 $1$。遍歷哈希表結(jié)束之后即可得到差為 $k$ 的數(shù)對的數(shù)目。

當(dāng) $k>0$ 時，每個差為 $k$ 的數(shù)對由兩個不相等的整數(shù)組成，對于任意整數(shù) $\text{num}$，當(dāng) $\text{num}$ 和 $\text{num}+k$ 都在數(shù)組中出現(xiàn)時，有數(shù)對 $(\text{num},\text{num}+k)$。遍歷數(shù)組 $\text{nums}$ 并用哈希集合記錄出現(xiàn)的數(shù)字，然后遍歷哈希集合，對于哈希集合中的每個數(shù)字 $\text{num}$，如果 $\text{num}+k$ 也在哈希集合中，則將數(shù)對的數(shù)目加 $1$。遍歷哈希集合結(jié)束之后即可得到差為 $k$ 的數(shù)對的數(shù)目。

代碼

class Solution {public int findPairs(int[] nums, int k) {int pairs = 0;if (k == 0) {Map<Integer, Integer> map = new HashMap<Integer, Integer>();for (int num : nums) {map.put(num, map.getOrDefault(num, 0) + 1);}Set<Integer> set = map.keySet();for (int num : set) {if (map.get(num) > 1) {pairs++;}}} else {Set<Integer> set = new HashSet<Integer>();for (int num : nums) {set.add(num);}for (int num : set) {if (set.contains(num + k)) {pairs++;}}}return pairs;}
}

復(fù)雜度分析

• 時間復(fù)雜度：$O(n)$，其中 $n$ 是數(shù)組 $\text{nums}$ 的長度。需要遍歷數(shù)組一次，使用哈希表或哈希集合存儲數(shù)組中的不同數(shù)字，然后遍歷哈希表或哈希集合一次，由于哈希表或哈希集合中的元素個數(shù)不超過數(shù)組長度，因此時間復(fù)雜度是 $O(n)$。

• 空間復(fù)雜度：$O(n)$，其中 $n$ 是數(shù)組 $\text{nums}$ 的長度。需要使用哈希表或哈希集合存儲數(shù)組中的不同數(shù)字，最壞情況下需要存儲數(shù)組中的全部數(shù)字。