#剑指offer Day4 一类 “ 双指针 ”问题

1. 思路

双指针有两种情况。第一种就是两个指针以相同速度向中间靠近，实行“夹逼准则”，适合有序数组的算法题（即下面所说的两种）；第二种就是两个指针的运动速度不一样，即快慢指针，可以找出链表中环的开始位置。

2. 实例

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

//开始还在纠结乘积最小，后来转念一想，a+b=sum,a和b越远乘积越小，而一头一尾两个指针往内靠近的方法找到的就是乘积最小的情况。如果是乘积最大的情况就是一直找到两个指针重合，每次找到一个就将之前返回的结果向量清空然后更新为新找到的。
class Solution {
public:
    vector<int> FindNumbersWithSum(vector<int> array,int sum) {
        vector<int> result;
        int length = array.size();
		int start = 0;
		int end = length - 1;
		while (start < end)       
		{
			if (array[start] + array[end] == sum)    // 找到了
			{
				result.push_back(array[start]);   // 把这两个数字push进去
                result.push_back(array[end]);
				break;    // 一定要 break，不然就陷入死循环
			}
			else if (array[start] + array[end] < sum)   // 如果小了，则左指针 右移
				start++;
			else
				end--;    // 如果大了，右指针左移
		} 
        return result;
    }
};

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

//左神的思路，双指针问题
//当总和小于sum，大指针继续+
//否则小指针+
class Solution {
public:
    vector<vector<int> > FindContinuousSequence(int sum) {
        vector<vector<int> > allRes;
        int phigh = 2,plow = 1;
        
        while(phigh > plow){
            int curSum = (phigh + plow) * (phigh - plow + 1) / 2;   // 等差数列求和公式
            
            if( curSum < sum)   // 如果当前和小于 sum，则右指针后移；
                phigh++;
            
            if( curSum == sum){         // 如果当前和等于 sum，那就把这个等差数列保存起来，push到res里面
                vector<int> res;
                for(int i = plow; i<=phigh; i++)
                    res.push_back(i);
                allRes.push_back(res);
                plow++;      // 再去找下一个
            }
     
            if(curSum > sum)    // 如果当前和小于 sum，则左指针右移
                plow++;
        }
       
        return allRes;     // 返回所有答案
    }
};