1.题目
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.
翻译:给定一组整数队列和一个整数K,你需要找到这个队列里唯一的 k-区别 数对的个数。在本题中,k-区别数对被定义为一个整数对(i,j),当i和j都是队列中的数且他们的绝对差是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:
- The pairs (i, j) and (j, i) count as the same pair.
- The length of the array won't exceed 10,000.
- All the integers in the given input belong to the range: [-1e7, 1e7].
2.思路
超时思路(每次都要先经历个超时思路真的是心累):首先将数组由小到大进行排序。初始化一个HashSet来记录已遍历过的元素,防止 k-差别 对儿不满足unique的条件。内层循环 j 从 i+1 开始,如果nums[j]和nums[j+1]相等,则j+1,即如果有几个相同值的元素,只对最后一个进行判断,如果nums[j]-nums[i]为k,则pairs+1;(pairs为满足条件的数组对儿数量)。
Accepted思路(24ms):
①判断特殊情况,数组长度小于等于1 或者 k<0 则返回0.(其中k<0这一情况容易被忽视,因为绝对差一定是大于等于 0的)。
②剩余 k>0和k==0两种情况。依旧使用一个HashSet(命名为set记录遍历过的数组中元素)。
a. k>0的情况中,遍历nums中的每一个元素,如果当前元素nums[i]不在集合set中(即同样大小的元素未被遍历过),但同时nums[i]-k在集合中,则pairs+1。将每一个nums[i]加到set中(这里不需要判断set中是否包含nums[i],HashSet的add方法会进行校验)。
b.k==0的情况中(即判断数组中有多少数量大于1的元素),遍历nums中的每一个元素,依旧用HashSet set来记录已遍历过的元素,同时需要新引入一个HashSet res来记录数量多于1的元素。对于遍历的每一个元素nums[i],如果它既在set中,同时又不在res中,则把它加入到res中,并且pairs+1(即第二次出现某一相同元素,会被加入到res中)。将每一个nums[i]加到set中。
3.算法
// TIMEOUT o(╥﹏╥)o
// public int findPairs(int[] nums, int k) {
// int len=nums.length;
// if(len<=1) return 0;
// Arrays.sort(nums);
// HashSet set=new HashSet();
// int pairs=0;
// for(int i=0;i set=new HashSet();
int pairs=0;
if(k>0){
for(int i=0;i res=new HashSet();
for(int i=0;i
4.总结
使用HashSet,算法的运行效率大大提升了。而且对于容易忽视的k<0的情况,对于算法的效率有很大影响。如果去掉对于k<0的处理,并把k>0的判断条件改为k!=0,则运行时间约为42ms,比当前的24ms慢很多。