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