和为S的连续正数序列
题目描述
小明很喜欢数学,有一天他在做数学作业时,要求计算出9~16的和,他马上就写出了正确答案是100。但是他并不满足于此,他在想究竟有多少种连续的正数序列的和为100(至少包括两个数)。没多久,他就得到另一组连续正数和为100的序列:18,19,20,21,22。现在把问题交给你,你能不能也很快的找出所有和为S的连续正数序列? Good Luck!
代码语言：javascript复制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
于是有如下代码：
代码语言：javascript复制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
已获授权
