K-diff Pairs in an Array trong C++

Cho mảng số nguyên và số k, tìm số cặp (i, j) duy nhất sao cho |i - j| = k. Cặp (i, j) và (j, i) coi như một.

Ví dụ: [3,1,4,1,5], k=2 → cặp (1,3) và (3,5) → kết quả 2.

Giải thuật

1. Nếu k < 0 trả về 0.
2. Dùng map freq đếm tần suất, set unique lưu các giá trị khác nhau.
3. Duyệt qua từng giá trị x trong set:
   • Nếu k == 0: cần freq[x] > 1 (cặp cùng giá trị).
   • Nếu k > 0: kiểm tra x + k có trong set không.
4. Đếm số cặp thỏa mãn.

Ví dụ triển khai C++

#include <bits/stdc++.h>
using namespace std;

class Solution {
public:
    int findPairs(vector<int>& nums, int k) {
        if (k < 0) return 0;
        unordered_map<int, int> freq;
        for (int x : nums) ++freq[x];
        
        int ans = 0;
        for (auto& [x, cnt] : freq) {
            if (k == 0) {
                if (cnt > 1) ++ans;
            } else {
                if (freq.count(x + k)) ++ans;
            }
        }
        return ans;
    }
};

int main() {
    Solution ob;
    vector<int> v = {3,1,4,1,5};
    cout << ob.findPairs(v, 2); // 2
    return 0;
}

Đầu vào / Đầu ra

Input: {3,1,4,1,5}, 2
Output: 2