532. K-diff Pairs in an Array

一開始我想法是先sort, 再用unordered_set像two sum那樣, 假設找到值就加加, 並在重複時跳過

但在以下測資會出錯

nums = [1,3,1,5,4], k = 0

因為重複的1被我跳過了, 所以我找不到結果, 但不跳過重複的話, count可能會多算

所以我就用set去紀錄存過的pair, 來幫忙濾掉重複的可能

class Solution {
public:
    int findPairs(vector<int>& nums, int k) {
        sort(nums.begin(), nums.end());
        unordered_set<int> m;
        set<pair<int, int>> res;
        for(int i = 0; i < nums.size();i++){
            if(m.count( nums[i] - k )){
                res.insert(make_pair(nums[i], nums[i] - k));
            }
            m.insert(nums[i]);
        }
        return res.size();
    }
};

可是光sort時間複雜度就是O(nlogn)了, 看到一種O(n)的做法

就是用一個table把所有數字出現的次數, 給記下來

如果k == 0, 任何數字只要大於1都合格

舉個例[1,1,2,2, 3] ->合格的有(1,1) (2,2), 3只有一個所以不行

如果k為>0的值我們就找另一個減去k的值

我一直納悶, 為什麼這邊我們只要找 x1 + k = x2 , 只有加呢, 明明人家碩的事|x1 — x2| = k, 理論上還有一個x1-k = x2啊

我們看一個例子

[-1, 1] k = 2
-1 + 2 = 1, 找得到所以答案加一
1 + 2 = 3, 找不到

這樣探討一個方向, 剛好可以規避掉(-1, 1) (1, -1)重複的組合

這方法很妙, 其實我覺得這提蠻好的只是不知道為何倒讚特別多

class Solution {
  public:
    int findPairs(vector<int> &nums, int k) {
unordered_map<int, int> m;
        int res = 0;
        for (int i = 0; i < nums.size(); i++) {
            m[nums[i]]++;
        }
        for (auto p : m) {
            if (k > 0 && m.count(p.first + k)) {
                res++;
            } else if (k == 0 && p.second > 1) {
                res++;
            }
        }
        return res;
    }
};