LeetCode 532. K-diff Pairs in an Array

Problem

LeetCode 532. K-diff Pairs in an Array

1. 题目简述

给出一个数组nums，一个整数k，找出数组内差绝对值为k的数组对的个数，（i,j）和（j, i）算同一个。例如：

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.

2. 算法思路

2.1 HashSet

首先，我们要想好用什么样的数据结构来存储。因为重复时，只计算一对，所以这种数据结构要有去重的效果，我们首先考虑Set，与此同时我们又发现，如果k=0的时候，我们又需要计算有重复的数有多少个，且2个重复的数和10个重复的数是一样的，在k=0时都只能算一对。所以单一的值存储不满足我们的需求，这时我们想到要用Map来存储，Key是值，Value是出现的次数。

Corner Cases：

1. k<0，nums为空数组或者null。
2. k=0，nums为(1, 1, 1, 2, 2)之类的有多组重复。

2.2 数组排序

如果我们仅利用数组的话，逻辑相对复杂，但速度会快一些，逻辑如下。

1. 首先将数组从小到大排序；
2. 定义lo和hi为两个pointer，初始值为0；n为数组长度
3. 当hi < n时，循环：如果lo >= hi，hi = lo + 1，循环继续；如果nums[hi] - nums[lo] < k，hi++；如果nums[hi] - nums[lo] > k，lo++；如果nums[hi] - nums[lo] = k，count++，lo++，且循lo++，直至下一个不同的值。

3. 解法

1. 注意hashMap的遍历方式

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

        if ((nums == null) || (nums.length == 0) || (k < 0)) {
            return 0;
        }

        int count = 0;
        Map<Integer, Integer> hashMap = new HashMap<Integer, Integer>();

        for (int i = 0; i < nums.length; i++) {
            if (hashMap.containsKey(nums[i])) {
                int value = hashMap.get(nums[i]);
                hashMap.put(nums[i], ++value);
            } else {
                hashMap.put(nums[i], 1);
            }
        }

        if (k == 0) {
            for (Map.Entry<Integer, Integer> entry : hashMap.entrySet()) {
                if (entry.getValue() > 1) {
                    count++;
                }
            }
        } else {
            for (Map.Entry<Integer, Integer> entry : hashMap.entrySet()) {
                if (hashMap.containsKey(entry.getKey() + k)) {
                    count++;
                }
            }  
        }

        return count;
    }
}