LeetCode.532.K-diff Pairs in an Array 数组中的k-diff数对

题目描述

532 K-diff Pairs in an Array
https://leetcode-cn.com/problems/k-diff-pairs-in-an-array/

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:

1. The pairs (i, j) and (j, i) count as the same pair.
2. The length of the array won’t exceed 10,000.
3. All the integers in the given input belong to the range: [-1e7, 1e7].

---

相似题目

LeetCode.001.Two Sum 两数之和
LeetCode.653.Two Sum IV - Input is a BST 两数之和4-输入是BST
LeetCode.532.K-diff Pairs in an Array 数组中的k-diff数对

LeetCode.016.3Sum Closest 最接近的三数之和
LeetCode.015.3Sum 三数之和

---

解题过程

用Map或者说哈希来实现 O(n)
分为k=0和k!=0两种情况

public int findPairs(int[] nums, int k) {
    if (k < 0) {
        return 0;
    }
    int count = 0;
    // value -> 是否使用过
    Map<Integer, Boolean> map = new HashMap<>();
    for (int i = 0; i < nums.length; i++) {
        // 分为k=0和k!=0两种情况
        if (0 != k) {
            // 不重复处理元素
            if (!map.containsKey(nums[i])) {
                map.put(nums[i], false);
                if (map.containsKey(nums[i] + k)) {
                    count++;
                }
                if (map.containsKey(nums[i] - k)) {
                    count++;
                }
            }
        } else {
            if (!map.containsKey(nums[i])) {
                map.put(nums[i], false);
            } else {
                if (false == map.get(nums[i])) {
                    count ++;
                    map.put(nums[i], true);
                }
            }
        }
    }
    return count;
}

---

GitHub代码

algorithms/leetcode/leetcode/_532_KDiffPairsInArray.java
https://github.com/masikkk/algorithms/blob/master/leetcode/leetcode/_532_KDiffPairsInArray.java

---