双指针

所谓双指针，是利用两个指针对一个有序数组进行遍历，查找出符合要求的数据集合。相信大家都接触到了这种思维模式的解题方法，只是没有注意到罢了。

滑动窗口一般都是定义一个slow指针，然后一个fast指针不断向前滑动(循环遍历)，这个过程中我们要判断：

1. 是否找到了窗口，

2. 窗口时否满足要求

3. 窗口缩减等

例1：给定一个数组a[n]，求数组中是否存在两个数的和等于给定值sum并输出？

这个问题很常见，解决方法有很多种，这里我就不赘述，我讲的是用双指针遍历法的。首先数组不一定有序，对数组排序是必须的。那么便来到了这样一个场景：对有序数组如何遍历来求得符合要求的数据集合？双指针的解决方法如下：定义两个指针（i 和 j），分别指向数组头和尾，那么会出现如下三种情况：

1. 如果a[i]+a[j] == sum，那么很显然，只要输出这两个数，并把指针i+1和j-1指向下一个数即可。（这里不输出重复的组合）

2. 如果a[i]+a[j] > sum，说明当前遍历的数值偏大，所以可以把j-1以减小和的值，在继续比较。 如果a[i]+a[j] <

3. sum，说明当前遍历的数值偏小，同样为了加大和可以把i+1。

总的时间复杂度取决于排序即O(nlogn)。

题目描述：

输入一个递增排序的数组和一个数字S，在数组中查找两个数，是的他们的和正好是S，如果有多对数字的和等于S，输出两个数的乘积最小的。

输出描述:

对应每个测试案例，输出两个数，小的先输出。

function FindNumbersWithSum(array, sum){

if(!array || !array.length){

return [];

}

var result = [];

var product = [];

var head = 0, tail = array.length - 1;

while(head < tail){

var curr = array[head] + array[tail];

if(curr === sum){

result.push([array[head], array[tail]]);

product.push(array[head] * array[tail]);

tail--;

head++;

} else if(curr > sum){

tail--;

} else {

head++;

}

}

if(result.length === 0){

return [];

}

var min = Math.min.apply(null, product);

var index = product.indexOf(min);

return result[index];

}

题目描述：

小明很喜欢数学,有一天他在做数学作业时,要求计算出9~16的和,他马上就写出了正确答案是100。但是他并不满足于此,他在想究竟有多少种连续的正数序列的和为100(至少包括两个数)。没多久,他就得到另一组连续正数和为100的序列:18,19,20,21,22。现在把问题交给你,你能不能也很快的找出所有和为S的连续正数序列? Good Luck!

输出描述:

输出所有和为S的连续正数序列。序列内按照从小至大的顺序，序列间按照开始数字从小到大的顺序

思路：大体的思路为设定两个指针start,end表示序列的最小值和最大值，当序列的相加的值大于给定的sum值时，我们需要减去start对应的值，并递增start，否则，我们应该递增end

function FindContinuousSequence(sum)

{

// write code here

//两个起点，相当于动态窗口的两边，根据其窗口内的值的和来确定窗口的位置和大小

var plow=1,phigh=2;

//存放结果

var result=[];

if(sum<3){

return result;

}

while(plow<phigh){

//由于是连续的，差为1的一个序列，那么求和公式是(a0+an)*n/2

var cur=(plow+phigh)*(phigh-plow+1)/2;

var list=[];

//相等，那么就将窗口范围的所有数添加进结果集

if(cur===sum){

for(var i=plow;i<=phigh;i++){

// 满足条件的元素加入数组

list.push(i);

}

//满足条件的一组元素加入结果数组

result.push(list)

//指针移动

plow++

// //如果当前窗口内的值之和小于sum，那么右边窗口右移一下

}else if(cur<sum){

phigh++;

}else{

//如果当前窗口内的值之和大于sum，那么左边窗口右移一下

plow++;

}

}

return result;

}