找硬币
哈希表存储查找
直接用哈希表存储并查找i-1个面额里是否存在m-ai的面额,然后更新要输出的v1为最小
时间复杂度:O(n)
#include<iostream>
#include<cstring>
#include<algorithm>
#include<unordered_set>
#define INF 10000
using namespace std;
int main()
{
int n,m;
scanf("%d%d",&n,&m);
unordered_set<int> hash;
int v1 = INF, v2;//v2较小值最小的方案
//判断前面i-1个面额里面是否存在m - ai的面额->查询操作
for(int i = 0;i < n;i ++)
{
int a,b;
scanf("%d",&a);
b = m - a;
if(hash.count(b))//判断b(另一个数)是否存在,且a不在其中的情况下防止冲突
{
hash.insert(a);//先将a插到哈希表里面
//结果要v1最小,所以要交换a为小的
if(a > b) swap(a,b);
if(a < v1) v1 = a, v2 = b;
}
else hash.insert(a);
}
if(v1 == INF) puts("No Solution");
else printf("%d %d\n",v1,v2);
return 0;
}
双指针遍历性质
存在一个满足ai+aj >= m 的最大为: ai + aj = m
说人话:当i从左往右变大,j从右往左变小,利用单调性构建双指针
因为要满足单调性,那么少不了排序,因此时间复杂度:O(nlogn)
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 100010;
int n, m;
int w[N];
int main()
{
scanf("%d%d", &n, &m);
for (int i = 0; i < n; i ++ ) scanf("%d", &w[i]);
sort(w, w + n);
for (int i = 0, j = n - 1; i < j; i ++ )//我们只需要找最小的ai结果所以就直接从小到大扫i
{
while (i < j && w[i] + w[j] > m) j -- ;//每一个i都从后往前扫j,找到ai+aj>m为止,且i!=j
if (i < j && w[i] + w[j] == m)//把每一个ai+aj>m的情况作比较,查看是否等于m符合则打印
{
printf("%d %d\n", w[i], w[j]);
return 0;
}
}
puts("No Solution");
return 0;
}
虽然,用哈希表时间复杂度很理想,但大多数情况下,双指针比哈希表快,毕竟unordered_set常数大