双指针练习3
一、PAT甲级1048（题目已经过翻译）
1、题目描述
Eva去商场购物，他有各种面值的钱，他希望付款时只用两枚硬币。
输入格式，第一行输入N表示元素个数，输入M表示总价；第二行，输入各个面值的硬币
题意：给出一个数组中的若干个元素，现在给出一个和，要求从数组中找到两个元素，这两个元素求和结果与给出的期望和一致，如果存在则输出两个元素，不存在则返回No Solution
输入整数m，从n个元素的数组中找出两个元素a，b；a<=b；要求a+b=m，如果有多对结果则输出a最小的那一对。
2、算法思路
这道题有很多种方法求结果，这里我只做一种双指针的解法
方法一：暴力求解，对数组中元素依次求和，找出满足要求的所有可能下标，如果有多对解，就对a的值进行比较，每次都选择a最小的一对
分析：显然这个算法时间复杂度为O(n^2)，因为要使用两个指针依次遍历数组。
方法二：可以先让数组变有序，然后遍历数组找出符合要求的结果
分析：好的排序算法时间复杂度为O(nlogn)，最后一次遍历时间复杂度为O(n)，所以时间复杂度为O(nlogn)
3、算法描述
（1）对输入序列进行sort排序
（2）定义两个指针i和j，让i指向A[0]，j指向A[n]
（3）开始时移动j，让j递减，直到*j<=m
（4）开始计算*i+*j；如果相等则返回*i，*j；如果>m就让j--；如果小于m就让i++
4、核心代码
5、总结
这道题除了这种解法还有一种更好的解法，就是拿空间换时间，可以构造一个键值对，当然，可以构造很多种键值对，只要逻辑上满足即可。
原文：https://www.cnblogs.com/zyq79434/p/14864529.html