枚举+优化（3）——哈希表优化实例

//两重循环枚举，时间复杂度O(N^2)
#include <bits/stdc++.h>
using namespace std;
int n,k,a[100000];
set<pair<int,int>> myset;
int main()
{
    cin >> n >> k;
    for(int i = 0;i < n;i++)
        cin >> a[i];
    for(int i = 0;i < n;i++)
        for(int j = 0;j < n;j++)
            if(a[i] + k == a[j])
                myset.insert(make_pair(a[i],a[j]));
    cout<<myset.size()<<endl;
    return 0;
}

//时间复杂度O(N)
#include <bits/stdc++.h>
using namespace std;
int main()
{
    int n,k,x,ans = 0;
    unordered_set<int> myset;
    cin >> n >> k;
    for(int i = 0;i < n;i++)
    {
        cin >> x;
        myset.insert(x);
    }
    for(int x:myset)
        if(myset.find(x+k) != myset.end())
            ans++;
    cout << ans << endl;
    return 0;
}

#include <bits/stdc++.h>
using namespace std;
int main()
{
    int n,k,x,ans = 0;
    set<int> myset;
    cin >> n >> k;
    for(int i = 0;i < n;i++)
    {
        cin >> x;
        myset.insert(x);
    }
    set<int>:: iterator i = myset.begin();
    for(i;i != myset.end();i++)
        if(myset.find((*i) + k) != myset.end())
            ans++;
    cout << ans << endl;
    return 0;
}

#include <bits/stdc++.h>
using namespace std;
int main()
{
    int n,c,t,st;
    unordered_map<int,int> cnt;
    cin >> n;
    for(int i = 0;i < n;i++)
    {
        cin >> c;
        st = 0;
        for(int j = 0;j < c;j++)
        {
            cin >> t;
            st += t;//每次放入砖块，坐标就要移动
            if(j != c - 1)//除了最后一行外，每行都要记录缝隙数
                cnt[st]++;//cnt[st]的值表示坐标的st的缝隙数量
        }
    }
    int mx = 0;
    for(auto it:cnt)//找最大的缝隙数
        if(it.second > mx)
            mx = it.second;
    cout<<n - mx<<endl;
    return 0;
}