每天一道剑指offer-和为S的连续正数序列

乔戈里

发布于 2019-03-05 09:53:52

3460

发布于 2019-03-05 09:53:52

和为S的连续正数序列

题目描述

小明很喜欢数学,有一天他在做数学作业时,要求计算出9~16的和,他马上就写出了正确答案是100。但是他并不满足于此,他在想究竟有多少种连续的正数序列的和为100(至少包括两个数)。没多久,他就得到另一组连续正数和为100的序列:18,19,20,21,22。现在把问题交给你,你能不能也很快的找出所有和为S的连续正数序列? Good Luck!

public ArrayList<ArrayList<Integer> > FindContinuousSequence(int sum) {
}

输出描述

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

解析

将 1~(S/2+1)区间的数 n依次加入到队列中（因为从 S/2+1之后的任意两个正数之和都大于 S）：

将 n加入到队列 queue中并将队列元素之和 queueSum更新，更新 queueSum之后如果发现等于 sum，那么将此时的队列快照加入到返回结果 res中，并弹出队首元素（保证下次入队操作时队列元素之和是小于sum的）
更新 queueSum之后如果发现大于 sum，那么循环弹出队首元素直到 queueSum<=Sum，如果循环弹出之后发现 queueSum==sum那么将队列快照加入到 res中，并弹出队首元素（保证下次入队操作时队列元素之和是小于sum的）；如果 queueSum<sum那么入队下一个 n

于是有如下代码：

public ArrayList<ArrayList<Integer>> FindContinuousSequence(int sum) {    ArrayList<ArrayList<Integer>> res = new ArrayList();    if(sum <= 1){        return res;    }    LinkedList<Integer> queue = new LinkedList();    int n = 1, halfSum = (sum >> 1) + 1, queueSum = 0;    while(n <= halfSum){        queue.addLast(n);        queueSum += n;        if(queueSum == sum){            ArrayList<Integer> one = new ArrayList();            one.addAll(queue);            res.add(one);            queueSum -= queue.pollFirst();        }else if(queueSum > sum){            while(queueSum > sum){                queueSum -= queue.pollFirst();            }            if(queueSum == sum){                ArrayList<Integer> one = new ArrayList();                one.addAll(queue);                res.add(one);                queueSum -= queue.pollFirst();            }        }        n++;    }
    return res;}

我们发现 11~15和 20~24行的代码是重复的，于是可以稍微优化一下：

public ArrayList<ArrayList<Integer>> FindContinuousSequence(int sum) {    ArrayList<ArrayList<Integer>> res = new ArrayList();    if(sum <= 1){        return res;    }    LinkedList<Integer> queue = new LinkedList();    int n = 1, halfSum = (sum >> 1) + 1, queueSum = 0;    while(n <= halfSum){        queue.addLast(n);        queueSum += n;        if(queueSum > sum){            while(queueSum > sum){                queueSum -= queue.pollFirst();            }        }        if(queueSum == sum){            ArrayList<Integer> one = new ArrayList();            one.addAll(queue);            res.add(one);            queueSum -= queue.pollFirst();        }        n++;    }
    return res;}

出自：http://www.zhenganwen.top

已获授权

本文参与腾讯云自媒体分享计划，分享自微信公众号。

原始发表：2019-02-04，如有侵权请联系 cloudcommunity@tencent.com 删除

queue