javaaddoffer_剑指offer算法题041：和为S的连续正数序列

自由互联小编在求职找找工作期间剑指offer上的算法题刷了很多遍并且每道题自由互联小编当时都总结了一种最适合面试时手撕算法的最优解法。考虑到剑指offer算法题在面试中的高频出现并且每道题自由互联小编当时都总结了一种最适合面试时手撕算法的最优解法。考虑到剑指offer算法题在面试中的高频出现自由互联小编每天和大家分享一道剑指offer上的算法题以及自由互联小编总结的答案。下面是第041道剑指offer算法题

题目描述

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

输出描述

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

分析

直接上代码分析过程在代码注释中

import java.util.ArrayList;public class Solution { /* 首先分析这个序列的最长长度是多少因为结果中要求序列间按照开始数字从小到大顺序 开始数字越小序列长度越大最长长度可以从1开始计算 1 2 3 4 ...... n (1n)*n/2sum ——> 2sum n(n1)>n^2 ——> n s sum/2 - (n-1)/2 */ public ArrayList > FindContinuousSequence(int sum) { ArrayList> res new ArrayList>(); for(int n(int) Math.sqrt(2*sum);n>2;n--) {//n if( ((n0 0) ||((n0) 0.5*n ) { ArrayListlist new ArrayList(); for(int j0,ksum/n-(n-1)/2;j//j用来控制当前序列的长度的 list.add(k); } res.add(list); } } return res; }}猜你还想看

为什么美国程序员工作比中国程序员工作轻松、加班少张一鸣我的大学四年收获及工作感悟应届生薪资越来越高2020互联网大厂平均薪资出炉git 吐血总结三年 Git 使用心得、总结牛逼轰轰的飞机操作系统

长按扫码关注

及时收看更多精彩内容

博主今日头条大数据工程师专注求职 面经 源码 java 大数据技术分享

点击”阅读原文“领取5T精品资料面试总结、100实战项目

我知道你 “在看”