LeetCode如何解决数组中K-diff数对的问题

小编给大家分享一下LeetCode如何解决数组中K-diff数对的问题,希望大家阅读完这篇文章之后都有所收获,下面让我们一起去探讨吧!

多伦ssl适用于网站、小程序/APP、API接口等需要进行数据传输应用场景,ssl证书未来市场广阔!成为成都创新互联公司的ssl证书销售渠道,可以享受市场价格4-6折优惠!如果有意向欢迎电话联系或者加微信:028-86922220(备注:SSL证书合作)期待与您的合作!

一、题目描述

给定一个整数数组和一个整数 k, 你需要在数组里找到不同的 k-diff 数对。这里将 k-diff 数对定义为一个整数对 (i, j), 其中 i 和 j 都是数组中的数字,且两数之差的绝对值是 k。

示例 1:

  • 输入: [3, 1, 4, 1, 5], k = 2
  • 输出: 2

解释: 数组中有两个 2-diff 数对, (1, 3) 和 (3, 5)。尽管数组中有两个 1,但我们只应返回不同的数对的数量。

 

二、解题思路

利用两个数的绝对值之差为 k 的关系 x - y = k,推出 y = x - k 和 x = y + k:

  • saw 集合保存访问过的元素
  • diff 集合保存已找到的 k-diff 数对中的较小值
  • 遍历所有元素,判断当前元素是否符合下面 2 个条件之一
  • 如果 y = x - k (1 = 3 - 2) 在 saw 中,则在 diff 中加入较小值 x - k = 1
  • 如果 x = y + k (3 = 1 + 2)在 saw 中,则在 diff 中加入较小值 y = 1
  • 在 saw 中加入已访问的元素
  • 放回 diff 集合的大小(set 相同的元素只存放一次)

要注意 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();
  }
};
    
复杂度分析
  • 时间复杂度:O(n),只需要遍历一次数组
  • 空间复杂度:O(n),set 集合空间与数组大小 n 呈线性增长

看完了这篇文章,相信你对“LeetCode如何解决数组中K-diff数对的问题”有了一定的了解,如果想了解更多相关知识,欢迎关注创新互联行业资讯频道,感谢各位的阅读!


网站名称:LeetCode如何解决数组中K-diff数对的问题
文章链接:http://bzwzjz.com/article/ghjjpj.html

其他资讯

Copyright © 2007-2020 广东宝晨空调科技有限公司 All Rights Reserved 粤ICP备2022107769号
友情链接: 网站设计制作报价 做网站设计 成都网站建设公司 营销型网站建设 成都品牌网站建设 成都网站设计 成都网站建设 成都网站设计 网站建设 网站建设开发 营销型网站建设 定制网站建设多少钱 网站建设公司 成都网站建设 手机网站建设套餐 成都网站设计 网站制作 手机网站制作设计 盐亭网站设计 成都网站建设 成都网站建设公司 阿坝网站设计