双指针(滑动窗口)

2018-05-28

双指针

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

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

是否找到了窗口，
窗口时否满足要求
窗口缩减等

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

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

如果a[i]+a[j] == sum，那么很显然，只要输出这两个数，并把指针i+1和j-1指向下一个数即可。（这里不输出重复的组合）
如果a[i]+a[j] > sum，说明当前遍历的数值偏大，所以可以把j-1以减小和的值，在继续比较。如果a[i]+a[j] <
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;
}