小编给大家分享一下LeetCode如何解决数组中K-diff数对的问题,希望大家阅读完这篇文章之后都有所收获,下面让我们一起去探讨吧!
多伦ssl适用于网站、小程序/APP、API接口等需要进行数据传输应用场景,ssl证书未来市场广阔!成为成都创新互联公司的ssl证书销售渠道,可以享受市场价格4-6折优惠!如果有意向欢迎电话联系或者加微信:028-86922220(备注:SSL证书合作)期待与您的合作!
给定一个整数数组和一个整数 k, 你需要在数组里找到不同的 k-diff 数对。这里将 k-diff 数对定义为一个整数对 (i, j), 其中 i 和 j 都是数组中的数字,且两数之差的绝对值是 k。
示例 1:
解释: 数组中有两个 2-diff 数对, (1, 3) 和 (3, 5)。尽管数组中有两个 1,但我们只应返回不同的数对的数量。
利用两个数的绝对值之差为 k 的关系 x - y = k,推出 y = x - k 和 x = y + k:
要注意 set 中相同的元素只存放一次,所以对于 3 1 4 1 5 的情况,diff 集合中只会保存 1 个元素 1,表示只有一个 (1, 3) 数对。
class Solution {
public:
int findPairs(vector& nums, int k) {
if (k < 0)
return 0;
// 保存访问的元素
std::set saw;
// 保存 k-diff 数对中较小的那个
// 也可以保存较大的,只用来统计数对个数
std::set diff;
for (int i = 0; i < nums.size(); i++) {
// 检查数对中较小的数 1 是否在数组中:3 - 2 = 1
if (saw.find(nums[i] - k) != saw.end())
diff.insert(nums[i] - k); // 插入数对中较小的数 1
// 检查数对中较大的数 3 是否在数组中:1 + 2 = 3
if (saw.find(nums[i] + k) != saw.end())
diff.insert(nums[i]); // 插入数对中较小的数 1
saw.insert(nums[i]);
}
// 因为 set 中不存在重复元素
// 所以不同的元素个数代表不同的 k-diff 数对个数
return diff.size();
}
};
看完了这篇文章,相信你对“LeetCode如何解决数组中K-diff数对的问题”有了一定的了解,如果想了解更多相关知识,欢迎关注创新互联行业资讯频道,感谢各位的阅读!