C++代码 找硬币 –> 双指针算法
#include<iostream>
#include<algorithm>
using namespace std;
constexpr int N = 1e+5 + 10;
int n,m; // n 代表拥有硬币的数量, m表示应支付的金额
int arr[N]; // 开辟一个数组用于存储 n 个 硬币的金额
int main()
{
cin >> n >> m;
for(int i = 0; i < n; ++i) cin >> arr[i];
sort(arr,arr+n); // 对存储硬币的数组进行排序,注意排序范围是 arr, arr + n , 默认为升序排序
int j = n - 1; // j作为当前遍历数组的最后一个硬币的下标
for(int i = 0; i < j; ++i) // for循环遍历, 这里 i < j 即可, 不用写 i <= j ,具体看循环内容即知道没必要写相等的情况
{
while(i!=j && arr[i] + arr[j] >= m)
if(arr[i] + arr[j] == m)
{
cout << arr[i] << " " << arr[j] << endl;
return 0;
}
else --j;
}
cout << "No Solution" << endl;
return 0;
}
代码思路
这里的核心代码是上面的for循环及其里面的while循环,这里是经典的双指针算法,这里我们进入循环之前我们进行了升序排序,故 i 最初指向的就是最小的硬币金额,j指向的就是硬币最大的金额。然后判断这两个硬币的金额相加是否大于等于所需金额m, 若是进一步是否是等于m的,若是则直接输出我们的答案,return结束,因为我们先进行了排序,所以输出的V1,V2中,就算是后面还有其他解,此时输出的V1也一定是较小的那个。若此时相加的金额不等于所需的金额m,则执行else语句,将–j, 因为此时两个硬币相加的金额肯定是大于所需的金额,这时肯定是找小一点的,故–j,找到前一个硬币(经过排序肯定是前一个硬币 <= 后一个硬币), 然后重复判断,直到此时相加的金额比所需的小,因为再–j,已经没意义了,此时就已经小了,前面的只会更小,或者这时也有可能是 i == j,表示指向同一个硬币了,即遍历结束此时无解了。 若 i < j , 则for继续循环, 这之前由于一直–j, 所以对于与之前与 arr[i] 相加大于m的arr[j], 根本没必要再重新遍历了,因为重新遍历也只是判断出大于m,故直接从上次跳出while的下标j开始比较即可。