532. K-diff Pairs in an Array

Version #1 Two pointers
Time O(nlogn) Space O(1)
是2sum的另一个版本，求的是2minus
如果当前两数之差大于target，则slow++, 若小于target，则fast++
如果等于target,稍微复杂一点：
    1.count++
    2.fast++
    3.为了避免重复，这里要求右侧的fast指针不能指向两次相等的值，所以判断一下fast和fast - 1是否相等，如果相等则fast继续++。因为求的是两数之差，只要保证了右侧的fast不会重复，自然左侧的slow就不会重复

上面有一点需要注意， 如果slow == fast - 1此时diff依然大于target的话，slow++ 之后就会和fast重合，这是我们不希望看到的，所以要检查slow必须一直小于fast，否则fast++


97.88 %

public class Solution {
    public int findPairs(int[] nums, int k) {
        if (nums == null || nums.length <= 1 || k < 0) return 0;
        Arrays.sort(nums);
        int count = 0;
        int slow = 0, fast = slow + 1;
        while(fast < nums.length) {
         
            int diff = nums[fast] - nums[slow];
            if (diff == k) {
                count++;
                fast++;
                while (fast < nums.length && nums[fast] == nums[fast - 1]) fast++;
            } else if (diff < k) fast++;
            else slow++;
         
            if (slow >= fast) fast++;
        }
        return count;

    }
    /*
    //这道题是不用去重的，因为存在自减之后差为0的valid solution
    public int[] sortAndremoveDuplicates(int[] nums) {
        Arrays.sort(nums);
        //index is the last position of valid piece of array
        int index = 0;
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] != nums[index]) {
                index++;
                nums[index] = nums[i];
            }
        }
        int[] result = Arrays.copyOfRange(nums, 0, index + 1);
        return result;
    }
    */
}

Version #2 HashMap
Time O(n) Space O(n)
70.58 % 
public class Solution {
    public int findPairs(int[] nums, int k) {
        if (nums == null || nums.length <= 1 || k < 0) return 0;
        //key-number, value-count of occurance in the array
        Map<Integer, Integer> map = new HashMap<>();
        for (int num : nums) {
            if(!map.containsKey(num)) {
                map.put(num, 1);
            } else {
                map.put(num, map.get(num) + 1);
            }
        }
        int count = 0;
        for (Map.Entry<Integer, Integer> entry : map.entrySet()) {
            //System.out.println(entry.getKey() + " " + entry.getValue());
            if (k == 0) {
                if (entry.getValue() >= 2) count++;
            } else {
                if (map.containsKey(entry.getKey() + k)) count++;
            }
        }
        return count;
    }
}