Acwing 1532 找硬币

题目链接：

Acwing 1532 找硬币

解法1：双指针

思路：

因为要找最小的

所以左边的指针从小到大，右边的指针从大到小。左指针不动，右指针向左移动逐个判断。

如果符合条件则输出并退出。

如果不符合条件，左指针往前移动一位，右指针从头继续判断。

代码：

#include<iostream>
#include<algorithm>

using namespace std;

const int N = 100010;
int q[N];
vector<pair<int,int>> res;

int main()
{
    int n ,m;
    cin>>n>>m;

    for(int i = 0; i < n; i ++)cin>>q[i];

    //排序从小到大排序
    sort(q,q+n);

    //定义左右指针
    int l,r;
    l = 0, r = n;

    //首先左指针始终在右指针的左边，如果相等或者交叉则结束
    while( l < r )
    {
        r--;
        //判断条件：1.左右指针的值符合条件 2.左右指针没有重叠
        //又因为之前已经排序了，所以结果为最优结果，直接输出
        if(q[r] + q[l] == m && r != l)
        {
            cout<<q[l]<<' '<<q[r]<<endl;
            return 0;
        }else if(q[l] < (m - q[r])){//判断条件：左右指针的和小于要求的值，那么后面的也就无需判断了
            l ++;           //左指针往前一位
            r = n;          //右指针从头判断
        }
    }
    cout<<"No Solution"<<endl;

    return 0;
}

解法2：数组枚举

思路：

因为硬币的面值：1 ≤ M ≤ 1000

所以开辟一个数组，用于记录每个硬币面值的个数。查找的时候直接使用数组的下标进行查找即可。

时间复杂度为o(1)

然后对所有的硬币面值进行排序，从小到大开始匹配

代码：

#include<iostream>
#include<algorithm>
#include<unordered_map>

using namespace std;
const int N = 100010;
//用于存储硬币
int q[N];
//用于记录和查找硬币
int h[1010];

int main()
{
    int n,m;
    cin>>n>>m;

    //输入，硬币，并计数各个面值的硬币数量
    for(int i = 0; i < n; i ++){
        cin>>q[i];
        h[q[i]]++;
    }
    //排序
    sort(q,q+n);

    //经过排序，从小到大开始遍历
    for(int i = 0; i < n; i ++)
    {
        h[q[i]]--;//当前使用的要去掉一枚
        int res = m - q[i]; //获取另一枚硬币的面值
        if(h[res] > 0){ //查看时候有这个面值的硬币
            cout<<q[i] << ' '<<res<<endl;
            return 0;
        }
    }
    cout<<"No Solution"<<endl;

    return 0;
}