双指针练习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、总结
这道题除了这种解法还有一种更好的解法,就是拿空间换时间,可以构造一个键值对,当然,可以构造很多种键值对,只要逻辑上满足即可。