题解 | #和为S的连续正数序列#

和为S的连续正数序列

http://www.nowcoder.com/practice/c451a3fd84b64cb19485dad758a55ebe

1 思考

先直接用序列最大和模板套，忽略序列有序，不是求最大和的背景，浪费一半时间
确定双指针思路后，再尝试提交，一半时间在处理边界问题

1.1 没认真读题

和为S的连续正数序列
在想究竟有多少种连续的正数序列的和为100(至少包括两个数）

数字是已经排好序的，第二要求至少2个正数

先算和，再比较，可以避免很多细节问题，但是有额外除法的开销（数列求和哈）

坑点

alt

2 code

c++ 累计两小时，

c++
java


class Solution {
public:
    vector<vector<int> > FindContinuousSequence(int sum) {
        vector<vector<int> > outV;
        vector<int> inV;
        if(sum ==0){
            return outV;
        }
        
        int i = 1 ,j = 0;
        //初始值，累计花了15分钟
        //int localSum = 0, gSum = 0 , start = 0, end = 1;
        int  start = 1, end = 2, localSum = start, gSum = 0 ;
        //for(; i< sum ;i++){
            //累计花了5分钟，查while {}缺失
        while( start <end){
            //参考其他的代码，如果这里 等差数列求和的话，对于边界情况就比较容易处理，但是除法开销。
            if(localSum< sum){
                localSum += end;//end = i;
                end++;
            }else if( localSum == sum){
                //这里面的细节还比较多 //边界值，累计花了5分钟
                if(end-1 == start || sum <=2)
                    break;
                inV.clear();
                //排除边界，累计2分钟，左闭右开
                for(j = start; j<end ;j++) 
                    inV.push_back(j);
                outV.push_back(inV);
                //处理双指针，累计3分钟，add compensate
                localSum -= start;
                start++;
            }else{
                //如果当前窗口内的值之和大于sum，那么左边窗口右移一下
                //而当前的重置，就做不到以上效果，尝试减去start? 然后start也更新哈
                //localSum = i;//start = i;//end = i;
                localSum -= start;
                start++;
            }//else
        }//while //end for
        return outV;
        
    }
};


import java.util.ArrayList;
public class Solution {
    public ArrayList<ArrayList<Integer> > FindContinuousSequence(int sum) {
        //存放结果
        ArrayList<ArrayList<Integer> > result = new ArrayList<>();
        //两个起点，相当于动态窗口的两边，根据其窗口内的值的和来确定窗口的位置和大小
        int plow = 1,phigh = 2;
        while(phigh > plow){
            //由于是连续的，差为1的一个序列，那么求和公式是(a0+an)*n/2
            int cur = (phigh + plow) * (phigh - plow + 1) / 2;
            //相等，那么就将窗口范围的所有数添加进结果集
            if(cur == sum){
                ArrayList<Integer> list = new ArrayList<>();
                for(int i=plow;i<=phigh;i++){
                    list.add(i);
                }
                result.add(list);
                plow++;
            //如果当前窗口内的值之和小于sum，那么右边窗口右移一下
            }else if(cur < sum){
                phigh++;
            }else{
            //如果当前窗口内的值之和大于sum，那么左边窗口右移一下
                plow++;
            }
        }
        return result;
    }
}