Shulou(Shulou.com)06/01 Report--

Editor to share with you how LeetCode solves the problem of K-diff pairs in the array. I hope you will get something after reading this article. Let's discuss it together.

Description of the topic

Given an array of integers and an integer k, you need to find different k-diff pairs in the array. Here, the k-diff number pair is defined as an integer pair (I, j), where I and j are numbers in the array, and the absolute value of the difference between the two numbers 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 there are two 1s in the array, we should only return the number of different pairs.

Second, the way to solve the problem

By using the relation x-y = k in which the difference between the absolute values of two numbers is k, we deduce y = x-k and x = y + k:

Saw set saves visited elements the diff set saves the smaller value in the found k-diff number pair to traverse all elements to determine whether the current element meets one of the following two conditions if y = x-k (1 = 3-2) is in saw, then add the smaller value x-k = 1 in diff if x = y + k (3 = 1 + 2) in saw Then add a smaller value y = 1 to the diff and add the accessed elements to the saw to put back the size of the diff collection (elements with the same set are stored only once)

Note that the same element in set is stored only once, so in the case of 3-1-4-1-5, only 1 element 1 is saved in the diff collection, indicating that there is only one (1, 3) number pair.

Class Solution {

Public:

Int findPairs (vector& nums, int k) {

If (k < 0)

Return 0

/ / Save the accessed elements

Std::set saw

/ / Save the smaller one of the k-diff pairs

/ / you can also save larger ones, which are only used to count the number of pairs.

Std::set diff

For (int I = 0; I < nums.size (); iTunes +) {

/ / check whether the smaller number 1 in the pair is in the array: 3-2 = 1

If (saw.find (Nums [I]-k)! = saw.end ())

Diff.insert (Nums [I]-k); / / the smaller number 1 in the insertion pair

/ / check whether the larger number 3 in the number pair is in the array: 1 + 2 = 3

If (saw.find (Nums [I] + k)! = saw.end ())

Diff.insert (Nums [I]); / / insert the smaller number 1 in the pair

Saw.insert (nums [I])

}

/ / because there are no duplicate elements in set

/ / so different numbers of elements represent different pairs of k-diff numbers

Return diff.size ()

}

}

Complexity analysis time complexity: O (n), only need to traverse once array space complexity: O (n), set set space increases linearly with array size n

After reading this article, I believe you have a certain understanding of "how LeetCode solves the problem of K-diff pairs in the array". If you want to know more about it, you are welcome to follow the industry information channel. Thank you for reading!

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.