---
title: 3D 兩數之和
tags: solution
---

# D. 兩數之和

### binary search
將所有數字輸入完並排列後，窮舉每一個數字 $x$，並利用二分搜尋法去尋找相對的數字（相對的數字即為目標值減去當前數字 $x$ 的值）

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

int main(){

    int n, m;
    vector<int> arr;
    cin >> n >> m;
  
    for ( int i = 0 ; i < n; i++ ) {
        int temp;
        cin >> temp;
        arr.push_back( temp );
    }
  
    sort( arr.begin(), arr.end() );

    int cnt = 0;
    while ( !arr.empty() ) {
        vector<int> :: iterator it = lower_bound( arr.begin(), arr.end(), m - arr[0] );
        if ( it != arr.end() && *it + arr[0] == m ){
            cnt++;
            arr.erase( it );
        }
        arr.erase( arr.begin() );
    }
  
    cout << cnt << '\n';
  
    return 0;
}

###### provided by. `Huaish`

---
### multiset
利用multiset，存放值為 $\text{Target}-\text{Value}$，並在之後如果有加入新的數字的話，直接查詢是否能對應到multiset上的任何一個數字。
如果能查到，即代表此兩個數字會湊成一個目標值。

# include <iostream>
# include <set>
using namespace std;

int main(){
    freopen("out.txt","w",stdout);

    multiset<int> s;
    multiset<int>::iterator it;

    int N,M,n,i,ans = 0;

    cin>>N>>M;
    for(n = 0 ; n<N ; n++){
        cin>>i;
        it = s.find(M-i);

        if(it == s.end())
            s.insert(i);
        else{
            s.erase(it);
            ans++;
        }
    }

    cout<<ans<<'\n';

    for(it = s.begin() ; it != s.end() ; it++)
        cout<<*it<<' ';
}