【甲級PAT】-1048 Find Coins (25分)-Hash散列

題目描述

1048 Find Coins (25分)

給出 n （≤10​^5）個正整數和一個正整數 m（≤10^​3），問 n 個數字中是否存在一對數字 a 和 b （a <= b），使得 a + b = m 成立。如果有多對，輸出 a 最小的那一對。

思路

1. 本題采用散列法，以 int 型HashTable 數組存放每個出現的數字次數。若 HashTable[i] > 0 && HashTable[m - i] 大于0， 則找到了一對數。但是要注意， i == m - i 時，必須保證數字 i 的個數大于等于
2. 散清單的大小不需要 100000那麼大，因為 題中 m 的大小範圍為 1000之内，最多用到 1000之内的資料
3. i <= (m + 1) / 2 的範圍取值即可

#include <bits/stdc++.h>

using namespace std;
const int N=1005;
int HashTable[N];
int main()
{
    #ifdef ONLINE_JUDGE
    #else
        freopen("1.txt", "r", stdin);
    #endif

    int n,m;
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
    {
        int x;
        scanf("%d",&x);
        ++HashTable[x];
    }
    for(int i=1;i<=(m+1)/2;i++)
    {
        if(HashTable[i]&&HashTable[m-i])
        {
            if(i==m-i&&HashTable[i]<=1)
                continue;
            
            printf("%d %d", i, m - i);
            return 0;
        }
    }
    printf("No Solution");
    return 0;
}