算法基础——双指针练习3

本文主要是介绍算法基础——双指针练习3，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

双指针练习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、总结

　　这道题除了这种解法还有一种更好的解法，就是拿空间换时间，可以构造一个键值对，当然，可以构造很多种键值对，只要逻辑上满足即可。

这篇关于算法基础——双指针练习3的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！