K-diff Pairs in an Array

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).