双指针

id: two-pointer

双指针

经典题目

sum equal pair

题目描述

在一个序列a1,a2,⋯ ,an,(n⩽105)a_1,a_2,\cdots,a_n,(n \leqslant 10^5)中,查找两个元素他们的和为mm,保证一定存在这样的两个数,如果有多对数成立,输出一对较小值最小的那对

样例输入

9
21 4 5 6 13 65 32 9 23
37

样例输出

5 32

解析

暴力

STL map

二分查询

可以参考: [[…/…/recursion/binary_search/有序集上的操作.md]]

双指针法

开始证明Proof:\cal{Proof}:

对问进行抽象, 先对整个序列进行排序

A={a1,a2,a3,⋯ ,an},ai⩽ai+1 A = \{a_1,a_2,a_3,\cdots,a_n\}, a_i \leqslant a_{i+1}

其中a1a_1为最小值, ana_n为最大值,描述问题为:求有序集AA中和为sumsum的对数(ai,aj),i<j(a_i,a_j),i<j中aia_i最小的一对,且保证有解,记为f(1,n)f(1,n)

证明: 集合分解,分治

先用最小值a1a_1和最大值ana_n进行配对,会产生三种情况

  1. 和正好为所求,因为要求是a1a_1是序列中最小数,所以这就是答案,直接输出
  2. 和大于所求,易想到ana_n和最小值的和大于所求,那么ana_n和其它任何值的和都大于所求,所以ana_n不可能是答案,所以可以缩小答案所在区间为:f(1,n−1)f(1,n-1)
  3. 和小于所求,易想到a1a_1和最大值的和小于所求,那么a1a_1和其它任何值的和都小于所求,所以ana_n不可能是答案,所以可以缩小答案所在区间为f(2,n)f(2,n)

也就是说,我们不停的缩小答案所在的区间,因为答案一定存在,最终一定可以得到解.

证毕Q.E.D\cal{Q.E.D}

总结:在有序集上求和为定值的数,可以用双指针法

代码如下:

练习

参考