K-diff จับคู่ในอาร์เรย์ใน C++

สมมติว่าเรามีอาร์เรย์และจำนวนเต็ม k เราต้องหาจำนวนของคู่ k-diff ที่ไม่ซ้ำกันในอาร์เรย์ ในที่นี้ คู่ k-diff เป็นเหมือน (i, j) โดยที่ทั้ง i และ j มีอยู่ในอาร์เรย์ และความแตกต่างที่แน่นอนคือ k

ดังนั้น หากอินพุตเป็น [3,1,4,1,5] k =2 เอาต์พุตจะเป็น 2 เนื่องจากมี 2-diff คู่สองคู่ในอาร์เรย์เหมือน (1,3) และ ( 3,5).

เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -

• กำหนดแผนที่ที่เรียกว่าเห็นและทำแล้ว

• กำหนดหนึ่งชุด s

• ถ้า k <0 แล้ว −

  • คืนค่า 0

• สำหรับการเริ่มต้น i :=0 เมื่อ i <ขนาดของ nums ให้อัปเดต (เพิ่ม i ขึ้น 1) ให้ทำ -

  • (เพิ่มขึ้นเห็น[nums[i]] โดย 1)

  • ใส่ nums[i] ลงใน s

• ตอบ :=0

• สำหรับแต่ละองค์ประกอบใน s ให้ทำ -

  • ถ้า k เท่ากับ 0 แล้ว −

    • ถ้าเห็น[it]> 1 แล้ว −

      • (เพิ่มขึ้นทีละ 1)

  • มิฉะนั้น

    • เพิ่มขึ้นทำ[มัน] โดย 1

    • ถ้า (it + k) อยู่ในที่มองเห็นแต่ยังไม่เสร็จสิ้น −

      • (เพิ่มขึ้นทีละ 1)

    • ถ้า (มัน - k) อยู่ในที่มองเห็นแต่ไม่ทำเสร็จแล้ว −

      • (เพิ่มขึ้นทีละ 1)

• กลับมาอีกครั้ง

ตัวอย่าง

ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -

#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