Offer to come, dig friends take it! I am participating in the 2022 Spring Recruit Punch card activity. Click here for details

describe

Given an array of integers nums and an integer k, return the number of unique k-diff pairs in the array.

A k-diff pair is an integer pair (nums[i], nums[j]), where the following are true:

  • 0 <= i < j < nums.length
  • |nums[i] – nums[j]| == k

Notice that |val| denotes the absolute value of val.

Example 1:

Input: nums = [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.
Copy the code

Example 2:

Input: nums = [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).
Copy the code

Example 3:

Input: nums = [1,3,1,5,4], k = 0
Output: 1
Explanation: There is one 0-diff pair in the array, (1, 1).
Copy the code

Note:

1 <= nums.length <= 10^4
-10^7 <= nums[i] <= 10^7
0 <= k <= 10^7
Copy the code

parsing

Given an integer array nums and an integer k, return the number of unique k-diff pairs in the array. A k-diff pair is an integer pair (nums[I], nums[j]) where the following conditions are met:

  • 0 <= i < j < nums.length
  • |nums[i] – nums[j]| == k

The meaning of this question seems to be very simple and clear, but the pass rate is only 39%, that is because some boundary conditions were not found, and I also made mistakes twice when I did it. First of all, we need to know that the pairs of integers we find cannot be repeated, so we can count the cases once. In addition, we can see that the value of k may be 0 by looking at the constraints in the problem. If k is greater than 0, we can better deal with it. But when k==0 we’re looking for the same number and it needs to appear at least twice in NUMS, and we want to count it only once. So we can handle it like this:

  • The second condition can be changed to nums[j] = nums[I] + k if nums[j] = nums[I] + k
  • We then define a set result to hold pairs of integers that are guaranteed not to be duplicated
  • We execute the while loop when nums is not empty, then each time we loop nums.pop(0) to get the uppermost element a, and when a+k is in the remaining nums, we append (a, a+k) to result until the end of the loop
  • Finally, you just need to return the length of result

The time complexity is O(N), and the space complexity is O(N). Nums. length = 0 <= I < j < nums.length = 0 <= I < j < nums.length = 0 <= I < j < nums.length = 0 <= I < j < nums.length = 0 <= I < j < nums.length

answer

class Solution(object):
    def findPairs(self, nums, k):
        """
        :type nums: List[int]
        :type k: int
        :rtype: int
        """
        nums.sort()
        result = set()
        while nums:
            a = nums.pop(0)
            if a+k in nums:
                result.add((a, a+k))
        return len(result)


        	      
		
Copy the code

The results

In the linked links in the Python online submission. Memory Usage: Each node has 15.5 MB, less than 41.35% of Python online submissions for K-diff Pairs in an Array.Copy the code

The original link

Leetcode.com/problems/k-…

Your support is my biggest motivation