KdiffPairsInAnArray2 [source code]

public class KdiffPairsInAnArray2 {
static
/******************************************************************************/
public class Solution {
    public int findPairs(int[] nums, int k) {
        if (k < 0) return 0;
        Map<Integer, Integer> map = new HashMap<> ();
        Set<Integer> bag = new HashSet<>();
        for (int i : nums) {
            Integer count = map.get(i - k);
            if (count != null && count != 0) {
                bag.add(i - k);
            }
            count = map.get(i + k);
            if (count != null && count != 0) {
                bag.add(i);
            }
            map.put(i, 1);
        }
        return bag.size();
    }
}
/******************************************************************************/

    public static void main(String[] args) {
        KdiffPairsInAnArray2.Solution tester = new KdiffPairsInAnArray2.Solution();
        int[][] inputs = {
            {3, 1, 4, 1, 5}, {2}, {2},
            {1, 2, 3, 4, 5}, {1}, {4},
            {1, 3, 1, 5, 4}, {0}, {1},
            {1,2,3,4,5}, {-1}, {0},
            {1,2,3,4,5}, {1}, {4},
            {6,3,5,7,2,3,3,8,2,4}, {2}, {5},
        };
        for (int i = 0; i < inputs.length / 3; i++) {
            int[] nums = inputs[3 * i];
            int k = inputs[1 + 3 * i][0];
            int expected = inputs[2 + 3 * i][0];
            System.out.println(Printer.separator ());
            Printer.openColor("magenta");
            System.out.print(Printer.array(nums) + " AND " + k);
            Printer.closeColor();
            int output = tester.findPairs(nums, k);
            System.out.print(" -> " + output + ", ");
            Printer.openColor(output == expected ? "green" : "red");
            System.out.println("expected: " + expected);
            Printer.closeColor();
        }
    }
}

这个题目直观上跟2sum非常相似, 所以这里也干脆用2sum的两种思路都来做一下这个题目, ver1用的是sort之后的2pointer, 这里ver2用HashMap的思路;
不过这个题目其实HashMap唯一起到的作用就是一个count的作用(甚至可以用一个set来代替, 然后直接用contains来判断是否已经 存在), 这题不像2sum那样需要记录index, 所以map自带的这个mapping属性其实是没有用到的. 这种做法本质上就是一个利用历史信息存取对穷搜的优化;
然后set还是起到一个remove duplicate的作用, 这个还是一样的;

最后的速度并没有提升, 还是29ms.

这个是discussion里面一个只使用HashMap的解:

public class Solution {  
    public int findPairs(int[] nums, int k) {  
        if (nums == null || nums.length == 0 || k < 0)   return 0;  

        Map<Integer, Integer> map = new HashMap<>();  
        int count = 0;  
        for (int i : nums) {  
            map.put(i, map.getOrDefault(i, 0) + 1);  
        }  

        for (Map.Entry<Integer, Integer> entry : map.entrySet()) {  
            if (k == 0) {  
                //count how many elements in the array that appear more than twice.  
                if (entry.getValue() >= 2) {  
                    count++;  
                }   
            } else {  
                if (map.containsKey(entry.getKey() + k)) {  
                    count++;  
                }  
            }  
        }  

        return count;  
    }  
}

这个人的思路其实更加直接, 直接一个count(一行代码写count using HashMap, 你行吗?), 然后分析这个Map, 在分析的时候, 只往后数, 也就是类似于我说的impose order的技巧; 我自己的这个map解法最后确实没有考虑impose order, avoid duplicate完全是靠set完成的;

discussion上面还有一个挺有意思的解法:
Put all numbers n in Hashset S1.
Put all numbers n+k in HashSet S2.
The number of pairs are the intersection of the two Hashsets. Different conditions apply to k=0 or k<0.

public class Solution {  
    public int findPairs(int[] nums, int k) {  

        int ans = 0;  

        if(k<0) return ans;  

        Set<Integer> set1 = new HashSet<Integer> ();  
        Set<Integer> set2 = new HashSet<Integer> ();  

        if(k==0){  
                for(int n:nums){  
                    if(!set1.contains(n))  
                        {set1.add(n);}  
                    else{  
                        set1.remove(n);  
                        if(!set2.contains(n)) ans++;  
                        set2.add(n);  
                        }  
                }  
        }  
        else{  
            for(int n:nums){  
                set1.add(n);  
                set2.add(n+k);  
            }  
            set1.retainAll(set2);  
            ans = set1.size();  
        }  

        return ans;  
    }  
}

这个想法还是挺清奇的, 虽然最后代码并没有因此简化很多, 不过这个思路很有意思;

这个是discussion上面一个只用一个Map的思路: 虽然理论上并没有很大的先进性,毕竟1个set也能做了, 但是这个人的算法还是体现了很多内功:
We iterate through the input array exactly twice. The map is used to map each number in the array to the index in which it first appears in the array. After a number y in the array is used to count a pair (x,y), where y = x+k, we map y to -1 in order to avoid counting the same pair again.

public int findPairs(int[] nums, int k) {  
    if (k < 0) return 0;   
    Map<Integer, Integer> map = new HashMap();  
    int count = 0, n = nums.length;  
    for (int i=0, j=0; j<2*n; j++, i=j%n) {  
        if (!map.containsKey(nums[i])) map.put(nums[i], i);  
        Integer upper = map.getOrDefault(nums[i]+k, -1);  
        if (upper != -1 && upper != i) {  
            count++;  
            map.put(nums[i]+k, -1);  
        }  
    }  
    return count;  
}

首先, 有一个问题从来没有总结过: 怎么统计leftmost occurrence index? 统计rightmost很简单, 我们都知道, 一边走一边持续更新就行了, 最后剩下的一个一定是rightmost. 但是leftmost的做法, 就是保证只更新一次: 只在最开始when never been updated before的时刻才允许更新一次: 具体实现就像这里用一个conditional override来实现;

这个人的循环写法比较奇怪, 非要i,j两个变量都写在循环header里面. 其实比较好的办法是j可以写在header里面, i相当于一个mask(被mod之后的可以用来access的index), 最好还是写成一个放在循环内部的local;

另外他这里也impose了order, 这也是为什么他要走一个2pass(首尾相接的cycle):
这个是我post的一个回答:
@NiHao_Android Suppose we have ...,3,...,5,... and we are looking for k = 2. If we iterate only once, when we reach 3 we would be looking for 5 but up until this moment, the map does not know of any 5's existence yet since none has been encountered.

When we reach 5, we would only be looking for 7 in the map (he imposed an order to avoid counting duplicates), and we won't be able to ever find the pair (3,5) past the entry 5.

By iterating twice, when we reach 3 (and are looking for 5 in the map) in the second iteration (j >= n), we would have 5 in the map by now (since we already did one iteration) and the pair (3,5) would be able to be discovered.

这个算法应该看做是上面那个先全部count然后process map的算法思路的改进; 虽然实际上的速度估计差不多;

另外注意他这里这个-1操作细节上也是有讲究的:
首先你怎么理解别人的算法? 举一个例子, 比如是[1,3,5], 然后先走一遍, 看看他这个算法实际上是怎么走的, 然后你看不懂这个-1的操作, 那么我们假设一下没有这个-1操作, 然后再走一遍, 看看能不能在这个trace的过程中理解到他这个操作的意义; 如果理解了, 那么尝试找一个no-case, 也就是在没有-1操作的情况下会蒙混过关的case: false positive;

上面介绍的是一个一般的思路, 在这个题目上, 这个false positive case还是很好找的: [1,1,3,5]. 第二遍的时候第二个1也会hit, 假如没有-1的话, 这个时候count就多++了一次. 当然假如用一个set来collect的话, 这个问题也不用管了, 不过这个算法的本意就是想要减少这些collection的使用;

Problem Description

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:
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].
Difficulty:Easy
Total Accepted:18.3K
Total Submissions:65K
Contributor: murali.kf370
Companies
amazon
Related Topics
two pointers array
Similar Questions
Minimum Absolute Difference in BST