和为S的连续正数序列（双指针详解）

题目解析：

  题目是小明算数，这里不赘述！->题目链接<-
  看到这道题目的可以马上想到等差数列，这个题目可以换一种说法就是求有多少个等差数列的和为sum，可以直接用公式计算，但是公式计算个人感觉有一些复杂，觉得使用双指针更好一些，类似于TCP中的滑动窗口，根据窗口中的数值的和来确定窗口的位置和宽度，大了就向右缩小窗口，小了就向右扩大窗口，相等了就向右缩小一个位置，继续之前的比较。当窗口缩小到没有了，说明窗口之后的等差数列的和都是大于sum的，就可以结束查找了。

图解思路：

代码解析：

  说了这么多，大概代码也已经想出来了！

class Solution { public:vector<vector<int> > FindContinuousSequence(int sum) {//存放返回值vector<vector<int> >ret;int pRight = 2, pLeft = 1;while(pRight > pLeft){//计算窗口中数值的和int tmp = (pRight + pLeft)*(pRight-pLeft+1)/2;//如果窗口中的和比sum小，窗口向右扩大if(tmp < sum)pRight++;//如果窗口中的和比sum大，窗口向左缩小else if(tmp > sum)pLeft++;//否则窗口中的和与sum一样大，将窗口中的值保存到ret中else{vector<int> arr;for (int i = pLeft; i <= pRight; ++i){arr.push_back(i);}ret.push_back(arr);//这里强调要移动窗口的左边框，不能是窗口的右边框//因为右边的值较大，移动有边框可能会跳过一个符合条件的等差数列pLeft++;}}return ret;} };

总结

以上是生活随笔为你收集整理的和为S的连续正数序列（双指针详解）的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。