小明很喜欢数学,有一天他在做数学作业时,要求计算出9~16的和,他马上就写出了正确答案是100。但是他并不满足于此,他在想究竟有多少种连续的正数序列的和为100(至少包括两个数)。没多久,他就得到另一组连续正数和为100的序列:18,19,20,21,22。现在把问题交给你,你能不能也很快的找出所有和为S的连续正数序列?
数据范围：
进阶：时间复杂度)
进阶：时间复杂度
[编程题]和为S的连续正数序列
# -*- coding:utf-8 -*- class Solution: def FindContinuousSequence(self, tsum): # write code here if tsum <= 0: return [] if tsum == 2: return [] if tsum == 3: return [[1,2]] e = tsum//2 res = [] sums = 0 for i in range(2, e): temp = [] sums = 0 if i % 2 == 0: k = tsum // i m = i // 2 if tsum % i == 0: continue else: if k-m+1 <=0: continue for j in range(k-m+1, k+m+1): sums += j temp.append(j) if sums == tsum: res.append(temp) temp = [] sums = 0 elif i % 2 != 0: k = tsum // i m = i // 2 if tsum % i != 0: continue else: if k-m <= 0: continue for j in range(k-m, k+m+1): sums += j temp.append(j) if sums == tsum: res.append(temp) return sorted(res)
发表于 2019-08-13 23:25:12
回复(0)
更多回答
//左神的思路，双指针问题
//当总和小于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)
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 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)
引申：
如何求递增数组中两个数字和为目标的问题
[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)
相信所有人都看过剑指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)
(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)
//我竟然解了二元一次方程，我是菜鸟我怕谁。。
//(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)
我看了几天，吸纳了很多讨论的灵感，暂时总结出四种解法吧。
发表于 2018-08-28 11:18:48
回复(1)
# 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)
等差数列求和直接公式算
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)
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)
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)
这里我的代码做了优化，剑指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)
//思路就是小了尾巴往后走，大了头部往后走，保证至少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)
/*
直接用数学方法做的
等差数列公式 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)
/*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)
这一题啊，我只想找到一个比我更简洁的代码，有没有比我更简洁的？？？？？？
上面第一个代码是第一遍写的，当时写了这么吊的代码竟然没有出来分享一下实在不符合自己的风格。下面是自己刷第二遍的时候写的代码，无论运行速率还是其他都比不上第一遍的，但是，我写这个代码花费的时间肯定是少于第一遍的，看看第一遍代码的精简程度，就知道第一遍代码写之前做了很多思考。
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条回答
2053收藏
133916浏览
通过挑战的用户
查看代码-
2023-02-25 23:08:42 -
2023-02-01 13:32:49
-
2022-10-28 15:47:54
-
2022-09-17 11:34:54
-
2022-09-16 16:08:43
相关试题
-
扫描二维码，关注牛客网
- 意见反馈
-
下载牛客APP，随时随地刷题
扫一扫，把题目装进口袋
- 求职之前，先上牛客
-
扫描二维码，进入QQ群
扫描二维码，关注牛客公众号
- 公司地址：北京市朝阳区北苑路北美国际商务中心K1座一层-北京牛客科技有限公司
- 联系方式：010-60728802 投诉举报电话：010-57596212（朝阳人力社保局）
- 牛客科技© All rights reserved admin@nowcoder.com
- 京ICP备14055008号-4 增值电信业务经营许可证 营业执照 人力资源服务许可证
-
京公网安备
11010502036488号
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; } }