首页 > itarticle > 【leetcode】532. k-diff pairs in an array

【leetcode】532. k-diff pairs in an array

admin 11月 13, 2020 0

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

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.

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 (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

AC

Analyse

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

Optimization

public int (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。