开发者社区> 李博 bluemind> 正文
阿里云
为了无法计算的价值
打开APP
阿里云APP内打开

[LeetCode] K-diff Pairs in an Array 数组中差为K的数对

简介: Given an array of integers and an integer k, you need to find the number of unique k-diff pairs in the array.
+关注继续查看

Given an array of integers and an integer k, you need to find the number of unique k-diff pairs in the array. Here a k-diff pair is defined as an integer pair (i, j), where i and j are both numbers in the array and their absolute difference is k.

Example 1:

Input: [3, 1, 4, 1, 5], k = 2
Output: 2
Explanation: There are two 2-diff pairs in the array, (1, 3) and (3, 5).
Although we have two 1s in the input, we should only return the number of unique pairs.

Example 2:

Input:[1, 2, 3, 4, 5], k = 1
Output: 4
Explanation: There are four 1-diff pairs in the array, (1, 2), (2, 3), (3, 4) and (4, 5).

Example 3:

Input: [1, 3, 1, 5, 4], k = 0
Output: 1
Explanation: There is one 0-diff pair in the array, (1, 1).

Note:

  1. The pairs (i, j) and (j, i) count as the same pair.
  2. The length of the array won't exceed 10,000.
  3. All the integers in the given input belong to the range: [-1e7, 1e7].

这道题给了我们一个含有重复数字的无序数组,还有一个整数k,让我们找出有多少对不重复的数对(i, j)使得i和j的差刚好为k。由于k有可能为0,而只有含有至少两个相同的数字才能形成数对,那么就是说我们需要统计数组中每个数字的个数。我们可以建立每个数字和其出现次数之间的映射,然后遍历哈希表中的数字,如果k为0且该数字出现的次数大于1,则结果res自增1;如果k不为0,且用当前数字加上k后得到的新数字也在数组中存在,则结果res自增1,参见代码如下:

解法一:

class Solution {
public:
    int findPairs(vector<int>& nums, int k) {
        int res = 0, n = nums.size();
        unordered_map<int, int> m;
        for (int num : nums) ++m[num];
        for (auto a : m) {
            if (k == 0 && a.second > 1) ++res;
            if (k > 0 && m.count(a.first + k)) ++res;
        }
        return res;
    }
};

下面这种方法没有使用哈希表,而是使用了双指针,需要给数组排序,节省了空间的同时牺牲了时间。我们遍历排序后的数组,然后在当前数字之后找第一个和当前数之差不小于k的数字,若这个数字和当前数字之差正好为k,那么结果res自增1,然后遍历后面的数字去掉重复数字,参见代码如下: 

解法二:

public:
    int findPairs(vector<int>& nums, int k) {
        int res = 0, n = nums.size(), j = 0;
        sort(nums.begin(), nums.end());
        for (int i = 0; i < n; ++i) {
            int j = max(j, i + 1);
            while (j < n && (long)nums[j] - nums[i] < k) ++j;
            if (j < n && (long)nums[j] - nums[i] == k) ++res;
            while (i < n - 1 && nums[i] == nums[i + 1]) ++i;
        }
        return res;
    }
};

 本文转自博客园Grandyang的博客,原文链接:K-diff Pairs in an Array 数组中差为K的数对,如需转载请自行联系原博主。

版权声明:本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。

相关文章
LeetCode每日一题——532. 数组中的 k-diff 数对
给定一个整数数组和一个整数 k,你需要在数组里找到 不同的 k-diff 数对,并返回不同的 k-diff 数对 的数目。
5 0
LeetCode015:除自身以外数组的乘积
LeetCode015:除自身以外数组的乘积
9 0
大数据基础之java常用API二(数组元素排序,冒泡排序、Arrays类,包装类,Date类)
大数据基础之java常用API二(数组元素排序,冒泡排序、Arrays类,包装类,Date类)
19 0
ACM 选手图解 LeetCode 最大二叉树
ACM 选手图解 LeetCode 最大二叉树
47 0
ACM 选手图解 LeetCode 对称二叉树
ACM 选手图解 LeetCode 对称二叉树
45 0
LeetCode 189:旋转数组 Rotate Array
公众号:爱写bug(ID:icodebugs) 给定一个数组,将数组中的元素向右移动 k 个位置,其中 k 是非负数。 Given an array, rotate the array to the right by k steps, where k is non-negative.
663 0
+关注
李博 bluemind
云栖社区Java、Redis、MongoDB运营小编,有意合作请联系钉钉:15810436147
文章
问答
文章排行榜
最热
最新
相关电子书
更多
低代码开发师(初级)实战教程
立即下载
阿里巴巴DevOps 最佳实践手册
立即下载
冬季实战营第三期:MySQL数据库进阶实战
立即下载