专栏首页尾尾部落[剑指offer] 和为S的连续正数序列

[剑指offer] 和为S的连续正数序列

题目描述

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

解题思路

滑动窗口的方法:用两个数字 start 和 end 分别表示序列的最小值和最大值,首先将 start 初始化为1,end 初始化为2。如果从start到end的和大于sum,我们就从序列中去掉较小的值(即增大start), 相反,只需要增大end。 终止条件为:一直增加begin到(1+sum)/2并且end小于sum为止

参考代码

import java.util.ArrayList;
public class Solution {
    public ArrayList<ArrayList<Integer> > FindContinuousSequence(int sum) {
        ArrayList<ArrayList<Integer> > res = new ArrayList<ArrayList<Integer> >();
        if(sum < 3)
           return res;
        int start = 1, end = 2, mid = (1+sum)/2;
        while(start < mid){
            int s = totalSum(start, end);
            if(s == sum){
                res.add(getSequence(start, end));
                end ++;
            }else if(s < sum){
                end ++;
            }else if(s > sum){
                start ++;
            }
        }
        return res;
    }
    public int totalSum(int start, int end){
        int sum = 0;
        for(int i = start; i <= end; i++){
            sum += i;
        }
        return sum;
    }

    public ArrayList<Integer> getSequence(int start, int end){
        ArrayList<Integer> temp = new ArrayList<>();
        for(int i = start; i <= end; i++){
            temp.add(i);
        }
        return temp;
    }
}

版权属于: 尾尾部落

原文地址: https://weiweiblog.cn/findcontinuoussequence/

转载时必须以链接形式注明原始出处及本声明。

window._bd_share_config={"common":{"bdSnsKey":{},"bdText":"","bdMini":"2","bdMiniList":false,"bdPic":"","bdStyle":"1","bdSize":"24"},"share":{}};with(document)0[(getElementsByTagName('head')[0]||body).appendChild(createElement('script')).src='http://bdimg.share.baidu.com/static/api/js/share.js?v=89860593.js?cdnversion='+~(-new Date()/36e5)];

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 使用自己的语料训练word2vec模型

    先对新闻文本进行分词,使用的是结巴分词工具,将分词后的文本保存在seg201708.txt,以备后期使用。

    尾尾部落
  • [剑指offer] 二叉树中和为某一值的路径

    输入一颗二叉树和一个整数,打印出二叉树中结点值的和为输入整数的所有路径。路径定义为从树的根结点开始往下一直到叶结点所经过的结点形成一条路径。

    尾尾部落
  • [剑指offer] 按之字形顺序打印二叉树

    请实现一个函数按照之字形打印二叉树,即第一行按照从左到右的顺序打印,第二层按照从右至左的顺序打印,第三行按照从左到右的顺序打印,其他行以此类推。

    尾尾部落
  • spring boot入门,看这篇文章就够了

    给maven 的settings.xml配置文件的profiles标签添加下面的代码:

    李红
  • spring boot入门,看这篇文章就够了

    给maven 的settings.xml配置文件的profiles标签添加下面的代码:

    李红
  • AAAI 2020 | 上交大:基于图像查询的视频检索,代码已开源!

    本篇文章介绍上海交通大学 BCMI 实验室在AAAI 2020 上的一项工作,A Proposal-based Approach for Activity Im...

    马上科普尚尚
  • 海上平台作业三维虚拟仿真

    海上平台是高出海面且具有水平台面的一种桁架构筑物,是在海上工作时在海水中搭建的便于人行走的仿陆地区域,供进行生产作业或其他活动使用,如在海底采石油、海上施工作业...

    HT for Web
  • [享学Eureka] 五、Eureka核心概念:应用(Application)和注册表(Applications)

    代码下载地址:https://github.com/f641385712/netflix-learning

    YourBatman
  • Hello Spring Boot

    Spring Boot 可以称之为 新一代 JavaEE 开发标准;随着动态语言的流行 (Ruby、Groovy、Scala、Node.js ),Java 的开...

    LCyee
  • python--的初级了解

    Unicode:2字节=16bit,2^16-1=65535      a-字节  你-2字节

    py3study

扫码关注云+社区

领取腾讯云代金券