Các cặp K-diff trong một mảng trong C ++

Giả sử chúng ta có một mảng và một số nguyên k, chúng ta phải tìm số cặp k-diff duy nhất trong mảng. Ở đây cặp k-diff giống như (i, j), trong đó i và j đều có mặt trong mảng và hiệu số tuyệt đối của chúng là k.

Vì vậy, nếu đầu vào giống như [3,1,4,1,5], k =2, thì đầu ra sẽ là 2, vì có hai cặp 2-diff trong mảng giống như (1,3) và ( 3,5).

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

• Xác định các bản đồ được gọi là đã xem và thực hiện

• Xác định một bộ s

• nếu k <0, thì -

  • trả về 0

• để khởi tạo i:=0, khi tôi

  • (tăng nhìn thấy [nums [i]] lên 1)

  • chèn nums [i] vào s

• ans:=0

• đối với mỗi phần tử nó trong s, do -

  • nếu k giống 0 thì -

    • nếu thấy [nó]> 1, thì -

      • (tăng ans lên 1)

  • Nếu không

    • tăng đã hoàn thành [nó] lên 1

    • nếu (it + k) được xem nhưng chưa hoàn thành, thì -

      • (tăng ans lên 1)

    • nếu (nó - k) được nhìn thấy nhưng không được thực hiện, thì -

      • (tăng ans lên 1)

• trả lại ans

Ví dụ

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

#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));
}

Đầu vào

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

Đầu ra

2