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

1. 思路

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

2. 实例

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

//开始还在纠结乘积最小，后来转念一想，a+b=sum,a和b越远乘积越小，而一头一尾两个指针往内靠近的方法找到的就是乘积最小的情况。如果是乘积最大的情况就是一直找到两个指针重合，每次找到一个就将之前返回的结果向量清空然后更新为新找到的。class Solution {public:    vector
   
     FindNumbersWithSum(vector
    
      array,int sum) {        vector
     
       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
   
    
      > FindContinuousSequence(int sum) {        vector
     
      
        > 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
       
         res;                for(int i = plow; i<=phigh; i++)                    res.push_back(i);                allRes.push_back(res);                plow++;      // 再去找下一个            }                 if(curSum > sum)    // 如果当前和小于 sum，则左指针右移                plow++;        }               return allRes;     // 返回所有答案    }};

转载地址：http://qmwki.baihongyu.com/

你可能感兴趣的文章