C ++中数组中的K-diff对

假设我们有一个数组和一个整数k，我们必须找到数组中唯一的k-diff对的数量。这里的k-diff对就像(i,j)，其中i和j都存在于数组中，它们的绝对差为k。

因此，如果输入像[3,1,4,1,5]，k = 2，则输出将为2，因为在类似数组(1,3)和（ 3,5）。

为了解决这个问题，我们将遵循以下步骤-

• 定义称为见过的和完成的映射

• 定义一组

• 如果k <0，则-

• 返回0

• 对于初始化i：= 0，当i <nums大小时，更新（将i增加1），执行-

• （将看到的[nums [i]]增加1）

• 在s中插入nums [i]

• 回答：= 0

• 对于s中的每个元素，执行-

• 完成[it]增加1

• 如果（it + k）可见但未完成，则-

• 如果(it-k)可见但未完成，则-

• （将ans增加1）

• （将ans增加1）

• 如果看到[它]> 1，则-

• （将ans增加1）

• 如果k等于0，则-

• 除此以外

• 返回ans

例 

让我们看下面的实现以更好地理解-

#include <bits/stdc++.h&g;
using namespace std;
class Solution {
public:
   int findPairs(vector<int>& nums, int k) {
      map<int, int> seen, done;
      set<int> s;
      if (k < 0)
         return 0;
      for (int i = 0; i < nums.size(); i++) {
         seen[nums[i]]++;
         s.insert(nums[i]);
      }
      int ans = 0;
      for (auto it = s.begin(); it != s.end(); it++) {
         if (k == 0) {
            if (seen[*it] > 1)
            ans++;
         }
         else {
            done[*it]++;
            if (seen.find(*it + k) != seen.end() && done.find(*it + k) == done.end())
               ans++;
            if (seen.find(*it - k) != seen.end() && done.find(*it - k) == done.end())
               ans++;
         }
      }
      return ans;
   }
};
main(){
   Solution ob;
   vector<int> v = {3,1,4,1,5};
   cout << (ob.findPairs(v, 2));
}

输入值

{3,1,4,1,5}, 2

输出结果

2