【Leetcode】532. 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

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

Solution

public int findPairs(int[] nums, int k) {
        Arrays.sort(nums);
        int len = nums.length;
        int count = 0;
        for (int i = 0; i < len;) {
            for (int j = i + 1; j < len;) {
                if (nums[j] - nums[i] == k) {
                    count++;
                }
                int n = 1;
                while (j + n < len && nums[j + n] == nums[j]) {
                    n++;
                }
                j += n;
            }
            int m = 1;
            while (i + m < len && nums[i + m] == nums[i]) {
                m++;
            }
            i += m;
        }
        return count;
    }

Result

Analyse

思路简单，复杂度O(n^2)，但是过了test case，问题不大。

Optimization

public int findPairs(int[] nums, int k) {
        if (nums == null || nums.length == 0 || k < 0)   return 0;
        Map<Integer, Integer> map = new HashMap<>();
        int count = 0;
        int len = nums.length;
        for (int i : nums) {
            map.put(i, map.getOrDefault(i, 0) + 1);
        }
        for (Map.Entry<Integer, Integer> entry : map.entrySet()) {
            if (k == 0) {
                if (entry.getValue() >= 2) {
                    count++;
                }
            } else {
                if (map.containsKey(entry.getKey() + k)) {
                    count++;
                }
            }
        }
        return count;
    }

Analyse

复杂度变为了O(n)，要习惯写map。