题目
给定一个整数数组和一个整数 k
,你需要在数组里找到 不同的 k-diff 数对,并返回不同的 k-diff 数对 的数目。
这里将 k-diff 数对定义为一个整数对 (nums[i], nums[j])
,并满足下述全部条件:
0 <= i < j < nums.length
|nums[i] - nums[j]| == k
注意,|val|
表示 val
的绝对值。
示例 1:
输入:nums = [3, 1, 4, 1, 5], k = 2
输出:2
解释:数组中有两个 2-diff 数对, (1, 3) 和 (3, 5)。
尽管数组中有两个1,但我们只应返回不同的数对的数量。
示例 2:
输入:nums = [1, 2, 3, 4, 5], k = 1
输出:4
解释:数组中有四个 1-diff 数对, (1, 2), (2, 3), (3, 4) 和 (4, 5)。
示例 3:
输入:nums = [1, 3, 1, 5, 4], k = 0
输出:1
解释:数组中只有一个 0-diff 数对,(1, 1)。
提示:
1 <= nums.length <= 10^4
-10^7 <= nums[i] <= 10^7
0 <= k <= 10^7
解题
方法一:哈希表
思路
首先考虑特殊情况:当 k == 0
时,问题就变成了求数组中有多少组重复元素,维护一个哈希表记录每个元素及其出现次数,循环数组更新哈希表,在某个元素出现第二次时把计数器(ans
)自增,最后返回 ans
即可。
对于更加一般的情况:首先把所有元素去重放入列表中,两层循环对于列表中每个元素把它和之后的每个元素作差,如果差的绝对值等于 k
就把计数器(count
)自增,最后返回 count
即可。
代码
class Solution {
public int findPairs(int[] nums, int k) {
if (k == 0) {
Map<Integer, Integer> map = new HashMap<>();
int ans = 0;
for (int num : nums) {
int count = map.getOrDefault(num, 0) + 1;
map.put(num, count);
if (count == 2) ans++;
}
return ans;
}
List<Integer> list = new ArrayList<>(new HashSet<>() {{
for (int num : nums) this.add(num);
}});
int n = list.size(), count = 0;
for (int i = 0; i < n - 1; i++) {
for (int j = i + 1; j < n; j++) {
if (Math.abs(list.get(j) - list.get(i)) == k) count++;
}
}
return count;
}
}
优化
在处理数组时都去重了为何不用树集顺便排个序?排序后还可以顺便剪个枝:如果内层循环某次算出的差值 diff
大于 k
就没必要继续循环了,直接 break
掉去判断下一个元素。
class Solution {
public int findPairs(int[] nums, int k) {
if (k == 0) {
Map<Integer, Integer> map = new HashMap<>();
int ans = 0;
for (int num : nums) {
int count = map.getOrDefault(num, 0) + 1;
map.put(num, count);
if (count == 2) ans++;
}
return ans;
}
List<Integer> list = new ArrayList<>(new TreeSet<>() {{
for (int num : nums) this.add(num);
}});
int n = list.size(), count = 0;
for (int i = 0; i < n - 1; i++) {
for (int j = i + 1; j < n; j++) {
int diff = list.get(j) - list.get(i);
if (diff == k) count++;
else if (diff > k) break;
}
}
return count;
}
}
方法二:哈希表
思路
维护两个集合 visited
存储之前已经遍历过的元素,ans
存储 k-diff 数对中较大的元素。
遍历数组,对于其中每个元素 num
:
- 如果在
visited
集合中可以找到num - k
,说明num
作为一组 k-diff 数对中较大的元素存在,把它加入ans
集合。 - 如果在
visited
集合中可以找到num + k
,说明num
作为一组 k-diff 数对中较小的元素存在,把跟它成一对的较大元素num + k
加入ans
集合。 - 把
num
加入visited
集合表示已经遍历过。
代码
class Solution {
public int findPairs(int[] nums, int k) {
Set<Integer> visited = new HashSet<>();
Set<Integer> ans = new HashSet<>();
for (int num : nums) {
if (visited.contains(num - k)) ans.add(num);
if (visited.contains(num + k)) ans.add(num + k);
visited.add(num);
}
return ans.size();
}
}
评论区