# K-diff Pairs in an Array

[https://leetcode.com/problems/k-diff-pairs-in-an-array/description/](https://leetcode.com/problems/k-diff-pairs-in-an-array/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).

## Thoughts

这道题的核心思想和2 sum很像，区别在于两个指针不是首尾，而是同在首，一个前一个后。让i指向当前最小，j指向次小，当nums\[i] + k > nums\[j]时，意味着最小和次小不能满足，让次小继续往前移动直到nums\[i] + k = nums\[j], 这时意味着最小元素i和移动到j的元素才能凑到大于等于nums\[i] + k。这时因为已经满足了或者超了，i元素不可能再和j以后的元素凑成pair了，所以i往前移动一个位置，看作把原i元素删除，i指向新的最小。这时需要把j重新在i+1位置开始吗？不需要，因为\[i-1, j] 区间的nums\[j] - nums\[i - 1]的才满足>=k, 现在i往前移动了一个位置, 那么nums\[j - 1] - nums\[i]肯定小于k。比如nums\[i-1] = 1, nums\[j] = 4, nums\[i] = 2。我们接着需要对新的最小元素nums\[i]重复以上过程。

## Code

```
class Solution {
    public int findPairs(int[] nums, int k) {
        Arrays.sort(nums);
        int i = 0, j = 1, res = 0;
        while (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 {
                i++;
                res++;
            }
        }

        return res;
    }
}
```

## Analysis

Errors:

1. 对于这道题nums\[i] == nums\[i - 1]时要直接往前移走。
2. j要永远保证在i的前面以防止出现当k=0时增加多余元素。

时间复杂度O(n), 空间O(1).
