剑指Offer打卡day—— ACWing 76. 和为S的连续正数序列-程序员宅基地

技术标签: 剑指offer打卡  双指针  前缀和  

【题目描述】
在这里插入图片描述

ACWing 76. 和为S的连续正数序列

【思路】
前缀和数组统计区间和
至少含有两个数 [a,b] a + b <=n 且要求a、b连续 b <= n / 2 + 1
那么枚举区间起点a和终点b

class Solution {
    
    long s[] = new long[100010];
    public List<List<Integer> > findContinuousSequence(int sum) {
    
        
        int t = (sum >> 1 )+ 1;  // 右移运算符比+优先级还弱 所以要加括号
        for(int i = 1; i <= t ; i ++)
            s[i] = s[i - 1] + i;
            
        List<List<Integer> > ans = new ArrayList<>();
        for(int b = 1; b <= t;  b ++){
    
            for(int a = 1; a < b; a ++){
    
                long res = s[b] - s[ a - 1];
                if(res == sum){
    
                    List<Integer> sub = new ArrayList<>();
                    for(int i = a; i <= b; i ++) sub.add(i);
                    ans.add(sub);
                }
            }
            
            
        }
        
        return ans;
       
    }
}

【思路】
双指针 等差数列前n项和公式

class Solution {
    
    public List<List<Integer> > findContinuousSequence(int sum) {
    
        
        int t = (sum >> 1) + 1;
        List<List<Integer> >  ans = new ArrayList<>();
       
        
        for(int i = 2, j = 1; i <= t;){
    
            int res = (i + j) * (i - j + 1) /2;
            if( res == sum ){
    
                List<Integer> sub = new ArrayList<>();
                int k = j; 
                while( k <= i) {
    
                    sub.add(k);
                    k ++;
                }
                ans.add(sub);
                //相等则 i、j同时右移
                i ++;
                j ++;
            }
            //如果当前区间和较小则i右移
            else if( res < sum) i ++;
            else j ++;
            
        }
        return ans;
       
    }
}
class Solution {
    
    public List<List<Integer> > findContinuousSequence(int sum) {
    
        // 至少由两个数组成 则最大值为sum/2 + 1
        int n = sum/2 + 1;
        // 前缀和数组
        int s[] = new int[n + 1];
        for (int i = 1; i <= n; i ++) {
    
            s[i] = s[i - 1] + i;
        }
        
        List<List<Integer>> ans = new ArrayList<>();
        // 枚举区间结尾端点
        for (int i = n, j = i - 1; i >= 2 && j >= 0;) {
    
           if (s[i] - s[j] == sum) {
     // 区间 [j + 1, i]符合条件
               List<Integer> sub = new ArrayList<>();
               for (int k = j + 1; k <= i; k ++) sub.add(k);
               ans.add(sub);
               i --;
           } else if (s[i] - s[j] < sum) {
     //区间[J+1, i]之和小于sum,j --
               j --;
           } else {
    
               i --;
           }
       }
       return ans;
    }
}
版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/weixin_44855907/article/details/117201941

智能推荐

9.任务段(TSS)_tss段-程序员宅基地

文章浏览阅读1k次。在调用门、中断门与陷阱门中,一旦出现权限切换,那么就会有堆栈的 ,切换。而且,由于CS的CPL发生改变,也导致了SS也必须要切换。切换时,会有新的ESP和SS(CS是由中断门或者调用门指定)这2个值从哪里来的呢?答案: TSS (Task-state segment ),任务状态段TSS就是一块内存,大小104个节不要把TSS与任务切换联系到一起TSS的意义就在于可以同时换掉一堆寄存器..._tss段

学习使用简单的php-程序员宅基地

文章浏览阅读47次。配置文件在:/etc/php5/$中,不同的模式含有自己的php.ini配置文件。php可以运行于多种模式:cgi、fastcgi、cli、web模块模式等4种;我现在使用的模式是cli模式,这里进行一次测试。在ubuntu下需要安装sudo apt-get install php5-devphp应该是php5的链接。修改config.m4文件:..._php 简单项目 为学习用

解决ios,iphone的safari浏览器h5自动放大,input获得焦点页面被放大_ios浏览器小于15像素的时候会进行放大-程序员宅基地

文章浏览阅读1.2k次。得到焦点之前设置font-size:16像素。_ios浏览器小于15像素的时候会进行放大

SpringBootAdmin 服务搭建记录_spring boot admin client与spring boot admin server都-程序员宅基地

文章浏览阅读520次。搭建过程网上很多, 主要是各个依赖的版本, 导致的各种 jar 包问题, 此处记录下我的 pom 和 yml 文件目录SpringAdmin server pom文件1. SpringAdmin server 配置(1) pom文件<parent> <groupId>org.springframework.boot</groupId> <artifactId>spring-boot-starter-p..._spring boot admin client与spring boot admin server都配置spring-boot-starter-

python3中图像识别的应用open-CV库_python open-cv 小图搜大图-程序员宅基地

文章浏览阅读1.4k次。python3中图像识别的应用open-CV库什么是open-CV?OpenCV是一个基于BSD许可(开源)发行的跨平台计算机视觉库,可以运行在Linux、Windows、Android和Mac OS操作系统上。它轻量级而且高效——由一系列 C 函数和少量 C++ 类构成,同时提供了Python、Ruby、MATLAB等语言的接口,实现了图像处理和计算机视觉方面的很多通用算法(百度百科)。代码:定义图像识别的类import cv2import osfrom PIL import ImageGr_python open-cv 小图搜大图

Linux下安装anaconda3_anaconda do you wish to process the-程序员宅基地

文章浏览阅读1w次,点赞2次,收藏19次。1.下载anaconda清华大学开源软件镜像站anaconda下载地址:https://mirrors.tuna.tsinghua.edu.cn/anaconda/archive/2.安装Anaconda$ sudo sh Anaconda3-5.3.0-Linux-x86_64.sh [sudo] andrew 的密码: Welcome to Anaconda3 5.3.0In o..._anaconda do you wish to process the

随便推点

k8s 安装 kubernetes-dashboard-2.X_kubernetes 2.x-程序员宅基地

文章浏览阅读10w+次。安装使用 k8s 原生的 web图形化界面_kubernetes 2.x

saltstack自动化运维管理——saltstack之salt远程执行_salt 远程执行命令-程序员宅基地

文章浏览阅读287次。目录一、Salt命令的构成1、target2、funcation3、arguments二、编写远程执行模块1、编写模块2、了解YAML语法3、SLS4、配置管理(1)方法一(2)方法二(3)方法三(4)一些例子一、Salt命令的构成Salt命令由三个主要部分构成:salt '<target>' <function> [arguments]1、targettarget: 指定哪些minion, 默认的规则是使用glob匹配minion id。salt '*' test._salt 远程执行命令

关于协方差,协方差矩阵的个人理解_协方差矩阵的ρ-程序员宅基地

文章浏览阅读1.9k次,点赞3次,收藏10次。文章目录协方差协方差定义举例说明方差相关系数协方差矩阵(covariance matrix)举例说明数学符号表示协方差矩阵的应用马氏距离数学符号定义PCA降维使用sklearn中的np.cov遇到的坑协方差协方差定义协方差(Covariance)在概率论和统计学中用于衡量两个变量的总体误差。设有随机变量XXX和随机变量YYY,则协方差定义为:Cov(X,Y)=E((X−E[x])(Y−E[Y]))=E((Y−E[Y])(X−E[X]))Cov(X,Y)=E((X-E[x])(Y-E[Y]))_协方差矩阵的ρ

【LaTeX】LaTeX/Algorithms 伪代码_latex algorithm return-程序员宅基地

文章浏览阅读1.5k次,点赞2次,收藏4次。algorithmic和algorithmicx介绍下algorithmic和algorithmicx,这两个包很像,很多命令都是一样的,只是algorithmic的命令都是大写,algorithmicx的命令都是首字母大写,其他小写(EndFor两个大写)。下面是algorithmic的基本命令。\STATE <text>\IF{<condition>} \STATE{<text>} \ENDIF\FOR{<condition>} \STATE{_latex algorithm return

Linux和Windows操作系统,MySQL数据库备份(导出)和恢复(导入)_.nb3文件如何打开-程序员宅基地

文章浏览阅读1.3k次。方式一:通过终端执行命令(适用于Linux操作系统)备份:将DATABASENAME数据库备份到/opt目录生成DATABASENAME.db备份文件mysqldump -uUSERNAME-pPASSWORD--routines --databases DATABASENAME> /opt/DATABASENAME.db登录MySQL:mysql -uUSERNAME -pPASSWORD删除数据库:drop database DATABASENAME;创建数据库:crea..._.nb3文件如何打开

推荐文章

热门文章

相关标签