KdiffPairsInAnArray [source code]

public class KdiffPairsInAnArray {
static
/******************************************************************************/
public class Solution {
    public int findPairs(int[] nums, int k) {
        Arrays.sort(nums);
        if (k < 0) return 0;
        Set<Integer> bag = new HashSet<>();
        int lo = 0, hi = 0;
        while (hi < nums.length) {
            if (nums[hi] - nums[lo] == k) {
                if (lo != hi) bag.add(nums[lo]);
                hi++;
            } else if (nums[hi] - nums[lo] < k) {
                hi++;
            } else {
                lo++;
            }
        }
        return bag.size();
    }
}
/******************************************************************************/

    public static void main(String[] args) {
        KdiffPairsInAnArray.Solution tester = new KdiffPairsInAnArray.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},
        };
        for (int i = 0; i < inputs.length / 3; i++) {
            int[] nums = inputs[3 * i];
            Arrays.sort(nums);
            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();
        }
    }
}

拿到一个题目, 先从笨办法开始想. 而不是一上来脑子里就是一些以前见过的聪明trick, 然后就想往这个题目上面套. 未必套的上去. 先想笨办法的好处就是, 当你有了笨办法的一个基本思路之后, 你熟悉的这些个trick突然你就会发现自然而然的知道怎么套到这个题目上来了;
比如这个题目, 一个立刻能想到的问题就是, 怎么avoid duplicate, 我立刻想到的做法就是impose order来做, 但是问题是你现在一个笨办法都没有, 你就算有这个trick你也不知道到底有什么用; 但是你看下面这个笨办法想出来之后, 这个impose order就知道怎么适应到这个问题了;

这个题目直观感受是类似2sum, 而且又是一个array题, 估计可以直接sort之后用2pointer来做;

这题k<0的情况他们认为是illegal, 其实就算是legal, 也很好处理, 直接相反数就行了;

这个问题整体思路还是比较简单的, sort完之后, 就可以用类似sliding window的方式来处理了; 唯一有点麻烦的是k = 0的情况, 这个情况下, 一个做法是, 干脆直接单独写一个算法, 就是数duplicate的, 很简单, 比如有5个1, 那么1能提供的pair数量就是5 - 1 = 4 这样; //好像还需要数, 就看哪些数有duplicate, 返回个数就行了, 不需要管实际上有多少个duplicate;
这里不是这样做的, 这里还是争取了把k = 0的算法也整合进去了, 具体的做法就是把第一个branch, 本来是让lo和hi都++的, 但是为了适应k=0的情况, lo++就删除了之后就好了. 具体什么原理可以自己走一个例子看看就知道了;

最后的速度是29ms (72%), 还可以接受;

这个是submission最优解: 14(99).

public class Solution {  
    public int findPairs(int[] nums, int k) {  
        if(k<0) return 0;  
        Arrays.sort(nums);  
        int left=0,right=1;  
        int res=0;  

        while(right<nums.length ){  
            if(nums[right]- nums[left]==k ){  
                res++;  
                int l=nums[left], r=nums[right];  
                while(left<right && nums[left]==l) left++;  
                while(right<nums.length && r==nums[right]) right++;  
            }else if(nums[right]- nums[left]<k ){  
                right++;  
            }else{  
                left++;  
                if(left==right) right++;  
            }  
        }  
        return res;  
    }  
}

思路一样的, 都是用sliding window走, 但是为了避免duplicate, 我的做法是刚开始是想用一个hash array来做, 不过后来想想不行, 这题的domain太大, 最后很可能会被OJ坑. 然后的想法就是用set来做.
他这里的方法更简单, 当发现一个新pair之后, 除了更新结果以外, 他直接让左右都变值(注意左右都要变, 因为假如只有一边变了, 那么最后的结果肯定不是k-diff). 注意他这里的while循环的写法: header里面的条件是yes-condition;
另外看看他这里第三个branch的处理: 我自己在走例子的时候, 碰到一个情况就是lo走的比hi要快, 这个就容易出问题, 而且这个问题的产生就是因为branch3产生的: 如果这个branch出现的次数多, left走的就多; 他的做法很直白, 在这个branch里面直接加一个conditional override来保证left不可能走的比right快就行了;

这个是discussion上面看到的一个类似的:

public class Solution {  
    public int findPairs(int[] nums, int k) {  
        Arrays.sort(nums);  

        int start = 0, end = 1, result = 0;  
        while (start < nums.length && end < nums.length) {  
            if (start == end || nums[start] + k > nums[end]) {  
                end++;  
            } else if (nums[start] + k < nums[end]) {  
                start++;  
            } else {  
                start++;  
                result++;  
                // start  
                //  |  
                // [1, 1, ...., 8, 8]  
                //              |  
                //             end  
                while (start < nums.length && nums[start] == nums[start - 1]) start++;  
                end = Math.max(end + 1, start + 1);  
            }  
        }  
        return result;  
    }  
}

思路其实都是一回事, 注意他们这种解法比我的解法优秀的一个地方在于, 他们不仅不用担心overhead, 而且他们的解法全都是O(1) space, 这个我是做不到的;

这里的两个loop其实是可以整合成一个loop的:

if (k < 0) return 0;  
Arrays.sort(nums);  
int ans = 0;  
for (int i = 0, j = 1; j < nums.length;) {  
    if (j <= i || nums[i] + k > nums[j]) {  
        j++;  
    } else if (i > 0 && nums[i] == nums[i - 1] || nums[i] + k < nums[j]) {  
        i++;  
    } else {  
        ans++;  
        i++;  
    }  
}  
return ans;

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