找硬币/两数之和(哈希表、双指针)
n个数和一个目标值,找到两个数使它们的和为目标值,若存在多个解使其中一个数为最小
- 哈希表
思路:循环每个数,判断和减去该数的结果是否在哈希表中,不在将数插入哈希表;在则判断数和结果中较小者是否小于当前最优解(要求存在多个解时使第一个数最小),将数插入哈希表。
#include<iostream>
#include<unordered_set>
using namespace std;
int main()
{
int n, m;
cin >> n >> m;
int v1 = 2000, v2;
unordered_set<int> hash;
for(int i = 0; i < n; i++)
{
int a, b;
cin >> a;
b = m - a;
if(hash.count(b))
{
if(a > b) swap(a, b); //始终使小的为v1
if(a < v1) v1 = a, v2 = b; //更新最优解
hash.insert(a);
}
else hash.insert(a);
}
if(v1 == 2000) cout << "No Solution";
else cout << v1 << ' ' << v2;
}
- 双指针
思路:循环每个数,每次循环中从后往前扫描是否存在与该数的和为目标数的数字,扫描到的第一个数即为结果。
#include<iostream>
#include<algorithm>
using namespace std;
int main()
{
int n, m;
int w[100010];
cin >> n >> m;
for(int i = 0; i < n; i++) cin >> w[i];
sort(w, w + n);
for(int i = 0, j = n-1; i < j; i++)
{
while(i < j && w[i] + w[j] > m) j--;
if(i < j && w[i] + w[j] == m)
{
cout << w[i] << ' ' << w[j];
return 0;
}
}
puts("No Solution");
return 0;
}