题目描述

输入一个正数 s,打印出所有和为 s 的连续正数序列(至少含有两个数)。

例如输入 15,由于 1+2+3+4+5=4+5+6=7+8=15,所以结果打印出 3 个连续序列 1~5、4~6 和 7~8。

样例

输入:15

输出:[[1,2,3,4,5],[4,5,6],[7,8]]

输出描述:

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

解法

用两个指针 p, q 指示序列的最小值和最大值。如果序列和大于 s,则从序列中去掉较小的值,即 ++p;如果序列和小于 s,则序列向右再包含一个数字,即 ++q

当 p 超过 s 的一半时,停止。

import java.util.ArrayList;
public class Solution {
public ArrayList<ArrayList<Integer> > FindContinuousSequence(int sum) {
ArrayList<ArrayList<Integer>> res = new ArrayList<>(); if(sum<3){
return res;
}
int p=1, q=2;
int mid = (1+sum) >> 1; //
int curSum = p + q; while(p < mid){ while(curSum > sum && p < mid){
curSum -= p;
p++;
//if(curSum == sum){
// res.add(getList(p, q));
// }
}
//这段代码不要上一个while之前,不然会代码重复,而且多了一次判断,效率不高
if(curSum == sum){
res.add(getList(p, q));
} ++q;
curSum += q;
}
return res;
} private ArrayList<Integer> getList(int l, int r){
ArrayList<Integer> res = new ArrayList<>();
for(int i=l; i<=r; i++){
res.add(i);
}
return res;
}
}

最新文章

  1. Java中的数是用补码表示的检验
  2. linux 下 ntfs移动硬盘挂载
  3. 今天想把iphone4刷成ios7.3beta,折腾半天,成功
  4. Redis介绍及实践分享
  5. MySQL特殊语法---replace into
  6. BaseAdapter导致notifyDataSetChanged()无效的四个原因及处理方法
  7. [译]关于Java 字符串最常被问到的十个问题
  8. 【差分+前缀和】BZOJ1637: [Usaco2007 Mar]Balanced Lineup
  9. 20165221 《网络对抗技术》EXP1 PC平台逆向破解
  10. 使用Java 线程池的利弊及JDK自带六种创建线程池的方法
  11. 有关mysql实现oracle分析函数功能的方法
  12. webservice调用和生成
  13. 保密数据!泽宝曝光各个主要店铺收入 核心SKU数量少得惊人
  14. datafactory5.6向mysql5.7添加大量测试数据
  15. FBI树-数据结构(二叉树)
  16. Thinkphp框架中自定义修改success和error页面
  17. 01-Jenkins-Master节点安装
  18. Terminal 快捷键帮助
  19. makefile 常用函数
  20. python之路---面向对象编程(一)

热门文章

  1. ssh-agent,ssh-add 命令
  2. CodeForces - 1007A (思维+双指针)
  3. python使用face_recognition包的环境设置
  4. 自定义MVC三
  5. ORM对象关系映射:
  6. CF798D Mike and distribution
  7. Python tempfile (临时文件)
  8. 设计模式-抽象工厂模式(AbstractFactory)(创建型模式)
  9. mysqltest语法整理
  10. [随笔]ICPC2.0