K-diff Pairs in an Array ใน C++

แนวคิด

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

เช่น ถ้าอินพุตคือ [3,1,4,1,5], k = 2 ผลลัพธ์คือ 2 เพราะมี 2-diff pairs สองคู่คือ (1,3) และ (3,5)

วิธีแก้:

• กำหนด map seen และ done
• กำหนดเซต s
• ถ้า k < 0: คืนค่า 0
• วนลูป i := 0 ถึงขนาด nums - 1: เพิ่ม seen[nums[i]] ขึ้น 1, แทรก nums[i] ลง s
• ans := 0
• สำหรับแต่ละ it ใน s:
  • ถ้า k เท่ากับ 0: ถ้า seen[it] > 1: เพิ่ม ans ขึ้น 1
  • มิฉะนั้น: เพิ่ม done[it] ขึ้น 1, ถ้า (it + k) อยู่ใน seen แต่ไม่อยู่ใน done: เพิ่ม ans ขึ้น 1, ถ้า (it - k) อยู่ใน seen แต่ไม่อยู่ใน done: เพิ่ม ans ขึ้น 1
• คืนค่า ans

ตัวอย่าง

#include <bits/stdc++.h>
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