首页 > 试题广场 >

和为S的连续正数序列

[编程题]和为S的连续正数序列
  • 热度指数：508536 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 256M，其他语言512M
  • 算法知识视频讲解
小明很喜欢数学,有一天他在做数学作业时,要求计算出9~16的和,他马上就写出了正确答案是100。但是他并不满足于此,他在想究竟有多少种连续的正数序列的和为100(至少包括两个数)。没多久,他就得到另一组连续正数和为100的序列:18,19,20,21,22。现在把问题交给你,你能不能也很快的找出所有和为S的连续正数序列?

数据范围：
进阶：时间复杂度

输出描述:
输出所有和为S的连续正数序列。序列内按照从小至大的顺序，序列间按照开始数字从小到大的顺序
示例1

输入

9

输出

[[2,3,4],[4,5]]
示例2

输入

0

输出

[]
算法知识视频讲解
查看答案及解析
添加回答
推荐
Java
我去个地方啊头像 我去个地方啊
在答案区找到一个答案，说的很好，叫做双指针技术，就是相当于有一个窗口，窗口的左右两边就是两个指针，我们根据窗口内值之和来确定窗口的位置和宽度。非常牛逼的思路，虽然双指针或者所谓的滑动窗口技巧还是蛮常见的，但是这一题还真想不到这个思路。 

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;
    }
}

编辑于 2019-02-13 19:50:27 回复(91)
C/C++
何恺明的小迷妹头像 何恺明的小迷妹 
//左神的思路，双指针问题
//当总和小于sum，大指针继续+
//否则小指针+
class Solution {
public:
    vector<vector<int> > FindContinuousSequence(int sum) {
        vector<vector<int> > allRes;
        int phigh = 2,plow = 1;
        
        while(phigh > plow){
            int cur = (phigh + plow) * (phigh - plow + 1) / 2;
            if( cur < sum)
                phigh++;
            
            if( cur == sum){
                vector<int> res;
                for(int i = plow; i<=phigh; i++)
                    res.push_back(i);
                allRes.push_back(res);
                plow++;
            }
            
            if(cur > sum)
                plow++;
        }
        
        return allRes;
    }
};

发表于 2016-08-09 11:03:00 回复(45)
renhao426头像 renhao426 
import java.util.ArrayList;
/*
*初始化small=1，big=2;
*small到big序列和小于sum，big++;大于sum，small++;
*当small增加到(1+sum)/2是停止
*/
public class Solution {
    public ArrayList<ArrayList<Integer>> FindContinuousSequence(int sum) {
    	ArrayList<ArrayList<Integer>> lists=new ArrayList<ArrayList<Integer>>();
        if(sum<=1){return lists;}
        int small=1;
        int big=2;
        while(small!=(1+sum)/2){          //当small==(1+sum)/2的时候停止
            int curSum=sumOfList(small,big);
            if(curSum==sum){
                ArrayList<Integer> list=new ArrayList<Integer>();
                for(int i=small;i<=big;i++){
                    list.add(i);
                }
                lists.add(list);
                small++;big++;
            }else if(curSum<sum){
                big++;
            }else{
                small++;
            }
        }
        return lists;
    }
    
    public int sumOfList(int head,int leap){        //计算当前序列的和
        int sum=head;
        for(int i=head+1;i<=leap;i++){
            sum+=i;
        }
        return sum;
    }
}


发表于 2016-08-11 15:56:44 回复(23)
Python
华科平凡头像 华科平凡

python solution

# -*- coding:utf-8 -*-
class Solution:
    def FindContinuousSequence(self, tsum):
        # write code here
        res=[]
        for i in range(1,tsum//2+1):
            sumRes=i
            for j in range(i+1,tsum//2+2):
                sumRes+=j
                if sumRes==tsum:
                    res.append(list(range(i,j+1)))
                    break
                elif sumRes>tsum:
                    break
        return res
发表于 2017-10-07 17:48:21 回复(8)
李思考考考考头像 李思考考考考 




/*
用两个数字begin和end分别表示序列的最大值和最小值，
首先将begin初始化为1，end初始化为2.
如果从begin到end的和大于s，我们就从序列中去掉较小的值(即增大begin),
相反，只需要增大end。
终止条件为：一直增加begin到(1+sum)/2并且end小于sum为止
*/

class Solution {
public:
    vector<vector<int> > FindContinuousSequence(int sum)
    { 
        vector<vector<int> > res;
        if(sum < 3) return res;
        int mid = (sum + 1)>>1;
        int begin = 1;
        int end = 2;
        int cur = begin + end;
        while(begin < mid && end < sum)
        {
            while(cur > sum)
            {
                cur -= begin;
                begin++;
            }
            if(cur == sum)
                InsertRes(begin,end,res);
             end++;
           	 cur += end;
        }
        return res;
    }
    void InsertRes(int begin,int end,vector<vector<int> > &res)
    {
        vector<int> temp;
        for(int i = begin;i<=end;i++)
            temp.push_back(i);
        res.push_back(temp);
    }
};

编辑于 2015-10-20 10:35:49 回复(9)
Python
Yannyezixin头像 Yannyezixin
引申：
如何求递增数组中两个数字和为目标的问题
[1, 2, 3, 4] 求出和为 5的两个数。 结果为[1, 4], [2, 3]
思路：
  • 维持最小变量small, 最大变量 big. 如果small + big == target, small向前移动一位，big向后移动一位
  • 如果small + big > target, 则要缩小和， big向前移动。否则, small向前移动增大和

回到本问题
  • 同样有small, big. 初始值为1, 2。target为N
  • 序列和(small到big) > target，同样要缩小和， small向前移动一位，则序列和减小small。否则增大和，big向前移动一位，序列和增大big
  • 如果相同，则保存下来。然后small向前移动两位， big向前移动一位（自己想想为什么)
  • 如此循环直到 small >= (1 + target) /2， 因为此时big + small 肯定大于target(题目要求最少两位） 

# -*- coding:utf-8 -*-
class Solution:
    def FindContinuousSequence(self, tsum):
        if tsum < 3:
            return []
        
        res = []
        small = 1
        big = 2
       	mid = (1 + tsum) / 2
        curSum = small + big
        
        while small < mid:
            if curSum == tsum:
                res.append(range(small, big + 1))
                small += 2
                big += 1
                curSum -= small * 2 - 3
                curSum += big
            elif curSum < tsum:
                big += 1
                curSum += big
            else:
                curSum -= small
                small += 1
        
        return res

编辑于 2016-07-27 12:03:44 回复(5)
Java
牛客司机头像 牛客司机
相信所有人都看过剑指offer书上的思想了，但是有的人Java实现还比较困难，分享一下我的解法。 
public ArrayList<ArrayList<Integer>> FindContinuousSequence(int sum) {
		ArrayList<ArrayList<Integer>> listAll = new ArrayList<ArrayList<Integer>>();
		if (sum < 3)
			return listAll;
		int small = 1;
		int big = 2;
		int middle = (sum + 1) / 2;
		int curSum = 3;
		while (small < middle) {
			while (curSum < sum) {
				big++;
				curSum += big;
			}
			if (curSum == sum) {
				ArrayList<Integer> list = new ArrayList<>();
				for (int i = small; i <= big; i++) {
					list.add(i);
				}
				listAll.add(list);
			}
			curSum -= small;
			small++;
		}
		return listAll;
	}

发表于 2016-08-06 11:15:58 回复(3)
马客(Mark)头像 马客(Mark)
(a + b)(b - a + 1) = sum * 2
设x = a + b, y = b - a + 1, y >= 2
枚举y，得x，解出a,b 

typedef vector<int> vi;
typedef vector<vi> vvi;
class Solution {
public:
    vvi FindContinuousSequence(int sum) {
        vvi res;
        sum <<= 1;
        for(int i = 2; i * i <= sum; ++i) if(sum % i == 0){
            int j = sum / i, t = (j - i + 1);
            if(!(t & 1)){
                res.push_back(vi());
                vi& v = res[res.size() - 1];
                t >>= 1;
                for(int a = t; a <= j - t; ++a) v.push_back(a);
            }
        }
        for(int i = 0, j = int(res.size()) - 1; i < j; ++i, --j) swap(res[i], res[j]);
        return res;
    }
};

发表于 2015-09-08 20:50:19 回复(7)
Java
村长，那人偷牛！头像 村长，那人偷牛！ 
//我竟然解了二元一次方程，我是菜鸟我怕谁。。
//(start+end)*(end-start+1)/2=sum; 
//根据start解出end。。。。。
public ArrayList<ArrayList<Integer> > FindContinuousSequence(int sum) {
         ArrayList<ArrayList<Integer>> result=new ArrayList<ArrayList<Integer>>();
        if(sum<3) return result;
        for(int i=1;i<=sum/2;i++){
            int value=1+4*i*i-4*i+8*sum;
            int valueSqrt=(int)Math.sqrt(value);
            if(value>=25&&valueSqrt*valueSqrt==value){
                ArrayList<Integer> path=new ArrayList<Integer>();
                for(int j=i;j<=(valueSqrt-1)>>1;j++)
                    path.add(j);
                result.add(path);
            }
        }
        return result;
    }

发表于 2017-05-04 00:36:54 回复(11)
C/C++
还有个太阳头像 还有个太阳
我看了几天，吸纳了很多讨论的灵感，暂时总结出四种解法吧。
发表于 2018-08-28 11:18:48 回复(1)
Hao_jiu_bu_jian头像 Hao_jiu_bu_jian 
# Python 感觉比较简短的代码了
class Solution:
    def FindContinuousSequence(self, tsum):
        # write code here
        l, r, sum, res = 1, 2, 3, []
        while l<r:
            if sum>tsum:
                sum -= l
                l += 1
            else:
                if sum==tsum:
                    res.append([i for i in range(l,r+1)])
                r += 1
                sum += r
        return res

编辑于 2017-08-01 14:57:10 回复(5)
C/C++
卷积神经网络哦头像 卷积神经网络哦

等差数列求和直接公式算

class Solution {
public:
    vector<vector<int> > FindContinuousSequence(int sum) {
        vector<int> tmp;
        vector<vector<int> > ans;
        for(int i = 1; i < sum; i++){
            double b = (sqrt(4*i*i-4*i+8*sum+1) - 1.0)/2.0;
            int b_int = floor(b + 0.5);
            if(abs(b - b_int) < 1e-3){
                for(int j = i; j <= b_int; j++) tmp.push_back(j);
                ans.push_back(tmp);
                tmp.clear();
            }
        }
        return ans;
    }
};
发表于 2018-12-20 09:30:58 回复(0)
Dejack头像 Dejack
Python solution: 两端加的方法，复杂度低 
def FindContinuousSequence(self, tsum):
    if tsum < 3:
        return []
    res, arr = [], [1, 2]
    middle = tsum // 2 + 1
    while arr and arr[0] < middle:
        if sum(arr) < tsum:
            arr.append(arr[-1] + 1)
        elif sum(arr) > tsum:
            arr.pop(0)
        else:
            res.append([i for i in arr])
            arr.append(arr[-1] + 1)
            arr.pop(0)
    if not arr:
        return []
    return res

编辑于 2018-10-11 19:11:44 回复(4)
shijiacheng头像 shijiacheng 
import java.util.ArrayList;

/**
 * 题目描述
 * 小明很喜欢数学,有一天他在做数学作业时,要求计算出9~16的和,他马上就写出了正确答案是100。
 * 但是他并不满足于此,他在想究竟有多少种连续的正数序列的和为100(至少包括两个数)。
 * 没多久,他就得到另一组连续正数和为100的序列:18,19,20,21,22。
 * 现在把问题交给你,你能不能也很快的找出所有和为S的连续正数序列? Good Luck!
 * 输出描述:
 * 输出所有和为S的连续正数序列。序列内按照从小至大的顺序，序列间按照开始数字从小到大的顺序
 *
 * @author shijiacheng
 */
public class FindContinuousSequenceSolution {
    public ArrayList<ArrayList<Integer>> FindContinuousSequence(int sum) {
        ArrayList<ArrayList<Integer>> result = new ArrayList<>();
        if (sum < 3){
            return result;
        }
        int small = 1;
        int big = 2;
        int curSum = small +big;
        int middle = (sum+1)/2;
        while (small<middle){
            if (curSum == sum){
                ArrayList<Integer> temp = new ArrayList<>();
                for (int i = small; i <= big; i++) {
                    temp.add(i);
                }
                result.add(temp);
            }

            while (curSum > sum && small<middle){
                curSum -= small;
                small++;

                if (curSum == sum){
                    ArrayList<Integer> temp = new ArrayList<>();
                    for (int i = small; i <= big; i++) {
                        temp.add(i);
                    }
                    result.add(temp);
                }
            }
            big++;
            curSum += big;
        }
        return result;
    }
}
发表于 2018-03-15 22:25:04 回复(0)
rainyan头像 rainyan
这里我的代码做了优化，剑指Offer上面给的参考答案其实不太好，存在着代码重复和条件不够完整的情况，附上我的代码和注释： 
class Solution {
public:
    vector<vector<int> > FindContinuousSequence(int sum) {
        vector<vector<int>> res;
        if(sum<3)
            return res;
		int begin = 1;
        int end = 2;
        //初始化curSum时直接用3，不要用a+b,这样效率会高一点
        int curSum = 3;
        int mid = (1+sum)>>1;
        //当begin<mid或者end<(mid+1)时，连续序列的和肯定超出sum了，所以这两个都要限制一下
        while(begin<mid && end<mid+1){
            while(curSum>sum){
                curSum -= begin;
                ++begin;
            }
            //这段代码不要上一个while之前，不然会代码重复，而且多了一次判断，效率不高
            if(curSum==sum)
                insertRes(begin,end,res);
            ++end;
            curSum += end;
        }
        return res;
    }
private:
    void insertRes(int a,int b,vector<vector<int>> &res){  vector<int> temp;
        for(int i=a;i<=b;++i)
            temp.push_back(i);
        res.push_back(temp);  }
};

发表于 2016-03-30 09:28:33 回复(3)
春天画花卉副校长头像 春天画花卉副校长 
import java.util.ArrayList;
public class Solution {
    public ArrayList<ArrayList<Integer> > FindContinuousSequence(int sum) {
        ArrayList<ArrayList<Integer> > alal = new ArrayList<ArrayList<Integer> >();
        for(int i = 1; i <= sum/2; i++){
            ArrayList<Integer> al = new ArrayList<>();
            int tempSum = i;
            int nextNum = i;
            al.add(i);
            while(tempSum < sum){
                 nextNum++;
                 al.add(nextNum);
                if((tempSum += nextNum) == sum){
                    alal.add(al);
                    break;
                }
               
            }
        }
        return alal;
    }
}

发表于 2015-10-11 10:47:45 回复(4)
丁满历险记头像 丁满历险记
1）由于我们要找的是和为S的连续正数序列，因此这个序列是个公差为1的等差数列，而这个序列的中间值代表了平均值的大小。假设序列长度为n，那么这个序列的中间值可以通过（S / n）得到，知道序列的中间值和长度，也就不难求出这段序列了。
2）满足条件的n分两种情况：
n为奇数时，序列中间的数正好是序列的平均值，所以条件为：(n & 1) == 1 && sum % n == 0；
n为偶数时，序列中间两个数的平均值是序列的平均值，而这个平均值的小数部分为0.5，所以条件为：(sum % n) * 2 == n.
3）由题可知n >= 2，那么n的最大值是多少呢？我们完全可以将n从2到S全部遍历一次，但是大部分遍历是不必要的。为了让n尽可能大，我们让序列从1开始，
根据等差数列的求和公式：S = (1 + n) * n / 2，得到.

最后举一个例子，假设输入sum = 100，我们只需遍历n = 13~2的情况（按题意应从大到小遍历），n = 8时，得到序列[9, 10, 11, 12, 13, 14, 15, 16]；n  = 5时，得到序列[18, 19, 20, 21, 22]。
完整代码：时间复杂度为 
import java.util.ArrayList;
public class Solution {
    public ArrayList<ArrayList<Integer> > FindContinuousSequence(int sum) {
        ArrayList<ArrayList<Integer>> ans = new ArrayList<>();
        for (int n = (int) Math.sqrt(2 * sum); n >= 2; n--) {
            if ((n & 1) == 1 && sum % n == 0 || (sum % n) * 2 == n) {
                ArrayList<Integer> list = new ArrayList<>();
                for (int j = 0, k = (sum / n) - (n - 1) / 2; j < n; j++, k++) {
                    list.add(k);
                }
                ans.add(list);
            }
        }
        return ans;
    }
}

编辑于 2018-01-25 16:18:35 回复(77)
搬一块叫CV的砖头像 搬一块叫CV的砖
//思路就是小了尾巴往后走，大了头部往后走，保证至少2个长度（start小于总和的一半，因为如果一个元素那必定是sum本身，肯定超过了（1+sum）/2）。终止条件就是start超过sum的一半。
vector<vector<int> > FindContinuousSequence(int sum) {
vector<vector<int> > result;
if (sum<3)
return result;
int start = 1;
int end = 2;
int middle = (1 + sum) / 2;
int curSum = start + end;
while (start<middle)
{
vector<int> tmp;
if (curSum == sum)
{
for (int i = start; i <= end; ++i)
tmp.push_back(i);
result.push_back(tmp);
tmp.clear();
}
while (curSum>sum&&start<middle)
{
curSum -= start;
start++;
if (curSum == sum)
{
for (int i = start; i <= end; ++i)
tmp.push_back(i);
result.push_back(tmp);
tmp.clear();
}
}
end++;
curSum += end;
}
return result;
}
发表于 2016-03-24 21:05:15 回复(1)
牛客000001号头像 牛客000001号 
/*
直接用数学方法做的
等差数列公式  2*n*a1+n(n-1)/2 = s; 由n>= 2 得 a1 <= (s - 1)/2
对首位数字a1从1到 (s - 1)/2遍历
等差数列公式变形   n*n+(2*a1 - 1)n-2s = 0
可得                        n = [-(2a - 1) + sqrt((2a - 1) * (2a - 1) + 8s)]/2
检验n是否为整数，是则得到一个答案
*/
vector<vector<int> > FindContinuousSequence(int sum) {
        vector<vector<int> > ans;
		int maxA1 = (sum - 1) / 2; //sum = n*a1 + n(n-1)/2 n最小为2 推导得到
		for(int i = 1; i <= maxA1; i++) //首位数字遍历
		{
			double f = (sqrt(double((2 * i - 1) * (2 * i - 1) + 8 * sum)) + 1 - 2 * i) / 2; //计算长度
			int n = int(f);
			if(abs(f - n) < 0.000001) //长度是整数，有效
			{
				vector<int> tempans;
				for(int j = 0; j < n; j++)
					tempans.push_back(i + j);
				ans.push_back(tempans);
			}
		}
		return ans;
    }

发表于 2015-07-14 22:25:56 回复(0)
Ron头像 Ron 
 

/*LinkedList.add复杂度低，所以用了LinkedList*/
public class Solution {
  	 public ArrayList<ArrayList<Integer>> FindContinuousSequence(int sum) {
        ArrayList<ArrayList<Integer>> resultList = new ArrayList<ArrayList<Integer>>();
    	if(sum <= 2){
        	return resultList;
        }
    	for(int start = 1;start <= (sum-1)/2; start++){
        	int end = start+1;
    		int seqSum = (start+end)*(end-start+1)/2;
    		LinkedList<Integer> result = new LinkedList<Integer>();
    		result.add(start);
    		while(seqSum <= sum){
    			result.add(end);
    			if(seqSum == sum){
    				resultList.add(new ArrayList<Integer>(result));
    				break;
    			}
    			end++;
    			seqSum = (start+end)*(end-start+1)/2;
    		}
    	}	  	
    	return resultList;
    }
}

编辑于 2015-07-08 15:41:06 回复(0)
辉88头像 辉88
这一题啊，我只想找到一个比我更简洁的代码，有没有比我更简洁的？？？？？？
上面第一个代码是第一遍写的，当时写了这么吊的代码竟然没有出来分享一下实在不符合自己的风格。下面是自己刷第二遍的时候写的代码，无论运行速率还是其他都比不上第一遍的，但是，我写这个代码花费的时间肯定是少于第一遍的，看看第一遍代码的精简程度，就知道第一遍代码写之前做了很多思考。 
    public ArrayList<ArrayList<Integer> > FindContinuousSequence(int sum) {
    	ArrayList<ArrayList<Integer> > lists = new ArrayList<ArrayList<Integer> >();
        for(int k = 2; k*k < 2*sum; k++){
        	double m = ((2.0*sum)/k-k+1)/2.0;
        	int temp = (int)m;
        	if(m == temp){
        		ArrayList<Integer> list = new ArrayList<Integer>();
        		for(int i = 0; i < k; i++){
        			list.add(i+temp);
        		}
        		lists.add(0, list);
        	}
        }
        return lists;
    }  public ArrayList<ArrayList<Integer> > FindContinuousSequence_(int sum) {
    	ArrayList<ArrayList<Integer> > Lists = new ArrayList<ArrayList<Integer> >();
        for(int i = 2; i <= sum/2+1; i++){
        	if(i%2 == 1){
        		if(sum%i == 0){
        			int temp = sum/i;
        			if(temp-i/2 > 0){
        				ArrayList<Integer> tempList = new ArrayList<Integer>();
        				for(int j = temp-i/2; j <= temp+i/2; j++){
        					tempList.add(j);
        				}
        				Lists.add(0,tempList);
        			}
        		}
        	}else{
        		int temp = sum/i;
        		double temp1 = temp+0.5;
        		if((int)(temp1 * i) == sum){
        			if(temp-i/2+1 > 0){
        				ArrayList<Integer> tempList = new ArrayList<Integer>();
        				for(int j = temp-i/2+1; j <= temp+i/2; j++){
        					tempList.add(j);
        				}
        				Lists.add(0,tempList);
        			}
        		}
        	}
        }
        return Lists;
    }
编辑于 2017-08-17 15:12:03 回复(1)
提交观点

问题信息

穷举
难度：
1429条回答 132934浏览

热门推荐

通过挑战的用户

查看代码

相关试题

和为S的连续正数序列

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号