| 每日一题做题记录，参考官方和三叶的题解 |
- 题目要求
- 思路一：哈希表
- Java
- C++
- Rust
- 思路二：离散化+双指针
- Java
- C++
- 不熟容器操作就放掉rust了
- 总结
- 一个类似模拟的思路。
- 用哈希表统计每个数出现的次数；
- 遍历每个数 c u r cur cur，找和它相差 k k k的另外一小一大两个数；
- 将 c u r cur cur的出现次数置 0 0 0，避免重复统计。
class Solution {
public int findPairs(int[] nums, int k) {
Map map = new HashMap<>();
for (int cur : nums)
map.put(cur, map.getOrDefault(cur, 0) + 1); // 放入哈希表计数
int res = 0;
for (int cur : nums) { // 枚举
if (map.get(cur) == 0)
continue;
if (k == 0) {
if (map.get(cur) > 1)
res++;
}
else {
int s = cur - k, b = cur + k; // 相差k的两个数
if (map.getOrDefault(s, 0) > 0)
res++;
if (map.getOrDefault(b, 0) > 0)
res++;
}
map.put(cur, 0);
}
return res;
}
}
- 时间复杂度： O ( n ) O(n) O(n)
- 空间复杂度： O ( n ) O(n) O(n)
class Solution {
public:
int findPairs(vector& nums, int k) {
unordered_map map;
for (int cur : nums)
map[cur] += 1; // 放入哈希表计数
int res = 0;
for (int cur : nums) { // 枚举
if (map[cur] == 0)
continue;
if (k == 0) {
if (map[cur] > 1)
res++;
}
else {
int s = cur - k, b = cur + k; // 相差k的两个数
if (map[s] > 0)
res++;
if (map[b] > 0)
res++;
}
map[cur] = 0;
}
return res;
}
};
- 时间复杂度： O ( n ) O(n) O(n)
- 空间复杂度： O ( n ) O(n) O(n)
- 用了rust的遍历函数iter()，所以在统计答案的时候就单向记录了，只找更大的（有序），既不漏也不会因为忘记置 0 0 0重复记录。
impl Solution {
pub fn find_pairs(nums: Vec, k: i32) -> i32 {
use std::collections::HashMap;
let mut map = HashMap::new();
nums.iter().for_each(|cur| *map.entry(*cur).or_insert(0) += 1);
map.iter().filter(|(cur, cnt)| k > 0 && map.contains_key(&(**cur + k)) || k == 0 && **cnt > 1).count() as i32
}
}
- 时间复杂度： O ( n ) O(n) O(n)
- 空间复杂度： O ( n ) O(n) O(n)
- 用数组替代哈希表，统计答案时操作数组下标。
- 先将原数组去重统计为 l i s t list list，然后记录每个数出现的次数 c n t cnt cnt用于统计答案；
- 遍历每个数 c u r cur cur，找和它相差 k k k的另外一小一大两个数 s , b s, b s,b；
- 左右指针分别指向不小于
s
s
s和
b
b
b的第一个数，根据其与
s
s
s和
b
b
b的关系统计答案。
- 这一步也可以用二分，从左右两端分别逼近 s s s和 b b b；
- 但因为 c u r cur cur是在不断增大的，那么 s s s和 b b b也会不断增大，所以指针会一直向后移动（因为 l i s t list list有序），所以用双指针更清晰简单。
class Solution {
static int[] cnt = new int[10010]; // 每个数出现的次数
public int findPairs(int[] nums, int k) {
Arrays.sort(nums);
List list = new ArrayList<>();
for (int cur : nums) {
if (list.isEmpty() || cur != list.get(list.size() - 1)) // 去重
list.add(cur);
}
Arrays.fill(cnt, 0);
for (int i = 0, j = 0; i < nums.length; i++) {
if (nums[i] != list.get(j))
j++;
cnt[j]++;
}
int n = list.size(), idx = 0, res = 0;
int left = 0, right = 0;
for (int cur : list) {
if (k == 0) {
if (cnt[idx] > 1)
res++;
}
else {
int s = cur - k, b = cur + k;
while (left < n && list.get(left) < s)
left++;
while (right < n && list.get(right) < b)
right++;
if (left < n && list.get(left) == s && cnt[left] > 0)
res++;
if (right < n && list.get(right) == b && cnt[right] > 0)
res++;
}
cnt[idx++] = 0;
}
return res;
}
}
- 时间复杂度： O ( n log n ) O(nlog n) O(nlogn)，排序离散化复杂度为 O ( n log n ) O(nlog n) O(nlogn)，统计答案复杂度为 O ( n ) O(n) O(n)
- 空间复杂度： O ( n ) O(n) O(n)
class Solution {
public:
int cnt[10010]; // 每个数出现的次数
int findPairs(vector& nums, int k) {
sort(nums.begin(), nums.end());
vector list;
for (int cur : nums) {
if (list.empty() || cur != list[list.size() - 1]) // 去重
list.emplace_back(cur);
}
memset(cnt, 0, sizeof(cnt));
for (int i = 0, j = 0; i < nums.size(); i++) {
if (nums[i] != list[j])
j++;
cnt[j]++;
}
int n = list.size(), idx = 0, res = 0;
int left = 0, right = 0;
for (int cur : list) {
if (k == 0) {
if (cnt[idx] > 1)
res++;
}
else {
int s = cur - k, b = cur + k;
while (left < n && list[left] < s)
left++;
while (right < n && list[right] < b)
right++;
if (left < n && list[left] == s && cnt[left] > 0)
res++;
if (right < n && list[right] == b && cnt[right] > 0)
res++;
}
cnt[idx++] = 0;
}
return res;
}
};
- 时间复杂度： O ( n log n ) O(nlog n) O(nlogn)，排序离散化复杂度为 O ( n log n ) O(nlog n) O(nlogn)，统计答案复杂度为 O ( n ) O(n) O(n)
- 空间复杂度： O ( n ) O(n) O(n)
只想到了哈希表的方法，还漏过了置 0 0 0的那一步。
后面略过了一种二分的方法（是真的不太喜欢二分），感觉用双指针更顺更有记忆点，基于数组有序所以左右指针也是只会向前的想法还是的。
| 欢迎指正与讨论！ |
