题解 | #农场牛类别匹配# 哈希表

知识点

哈希表

思路

显然暴力枚举匹配的时间复杂度为 $O(n^2)$ ; 在超时边缘了，我们就不讨论了；开一个哈希表来计数可以把时间复杂度降到 $O(n)$ 。

具体就是扫一遍数组，如果当前哈希表中有记录到和其互补的数字就减去一个互补的数字个数；否则当前数字个数+1。

开哈希表的常数比较大，实际上值域又不大，可以开个数组代替。

时间复杂度 $O(n)$

AC Code（C++）

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param breeds int整型vector 
     * @param target_sum int整型 
     * @return int整型
     */
    int countMatchingPairs(vector<int>& breeds, int target_sum) {
        int res = 0;
        vector<int> cnt(10010, 0);
        for (auto& x : breeds) {
            if (cnt[target_sum - x] > 0) {
                cnt[target_sum - x] -= 1;
                res += 1;
            }
            else {
                cnt[x] += 1;
            }
        }
        return res;
    }
};