当前位置: 首页 > news >正文

前缀和部分题目

前缀和

前缀和指数组的前 N项之和,是个比较基础的算法

例题

面试题 17.05. 字母与数字

给定一个放有字母和数字的数组,找到最长的子数组,且包含的字母和数字的个数相同。
返回该子数组,若存在多个最长子数组,返回左端点下标值最小的子数组。若不存在这样的数组,返回一个空数组。

示例 1:
输入: [“A”,“1”,“B”,“C”,“D”,“2”,“3”,“4”,“E”,“5”,“F”,“G”,“6”,“7”,“H”,“I”,“J”,“K”,“L”,“M”]
输出: [“A”,“1”,“B”,“C”,“D”,“2”,“3”,“4”,“E”,“5”,“F”,“G”,“6”,“7”]

示例 2:
输入: [“A”,“A”]
输出: []

提示:
array.length <= 100000

思路

使用前缀和+哈希
为字母则取1,数字为-1,即要求和为0的最大子数组。
前缀和表示第i个数及之前的所有数的和。哈希存储前缀和c第一次出现的位置i,循环时维护一个maxlen表示最大的子数组长度,start表示最长子数组起始下标。
初始化时,前缀和为0,下标为-1。遍历到i时,前缀和为sum,如果此时哈希表中没有关于前缀和为sum的记录,则更新indices[sum]=i。如果已有,则对比maxlen和i-indices[sum],如果i-indices[sum]较大,则maxlen更新为i-indices[sum],start更新为indices[sum]+1。
如果maxlen不为0,返回array中array[start]到array[start+maxlen]的部分。

代码

class Solution {
public:vector<string> findLongestSubarray(vector<string>& array) {int n=array.size();int sum=0;int maxlen=0;int start=-1;unordered_map<int,int> indices;indices[0]=-1;for(int i=0;i<n;i++){if(isalpha(array[i][0])){sum++;}else{sum--;}if(indices.find(sum)==indices.end()){indices[sum]=i;}else{if(i-indices[sum]>maxlen){maxlen=i-indices[sum];start=indices[sum]+1;}}}if(maxlen==0) return {};return vector<string>(array.begin()+start,array.begin()+start+maxlen);}
};

209. 长度最小的子数组

给定一个含有 n 个正整数的数组和一个正整数 target 。
找出该数组中满足其和 ≥ target 的长度最小的 连续子数组 [numsl, numsl+1, …, numsr-1, numsr] ,并返回其长度。如果不存在符合条件的子数组,返回 0 。

示例 1:
输入:target = 7, nums = [2,3,1,2,4,3]
输出:2
解释:子数组 [4,3] 是该条件下的长度最小的子数组。

示例 2:
输入:target = 4, nums = [1,4,4]
输出:1

示例 3:
输入:target = 11, nums = [1,1,1,1,1,1,1,1]
输出:0

提示:
1 <= target <= 109
1 <= nums.length <= 105
1 <= nums[i] <= 105

进阶:
如果你已经实现 O(n) 时间复杂度的解法, 请尝试设计一个 O(n log(n)) 时间复杂度的解法。

思路

首先计算前缀和,presum[i]表示从0加到i-1的和,
对于遍历每个子数组的起始点nums[i],用二分搜索找到presum[j]-presum[i]大于或等于target的第一个下标j,遍历过程中维护最短子数组的长度minlen。

或者用滑动窗口做

代码

//前缀和+二分搜索
class Solution {
public:int minSubArrayLen(int target, vector<int>& nums) {int n=nums.size();int minlen=n+1;vector<int> presum(n+1,0);//presum[i]是从0加到i-1for(int i=0;i<n;i++){presum[i+1]=presum[i]+nums[i];}for(int i=0;i<n;i++){int l=i+1,r=n;while(l<r){int m=(l+r)/2;if(presum[m]-target<presum[i]){l=m+1;}else{r=m;}}if(presum[l]-target>=presum[i]){minlen=min(l-i,minlen);}}if(minlen>n) return 0;else return minlen;}
};
class Solution {
public:int minSubArrayLen(int target, vector<int>& nums) {int n=nums.size();int l=0,r=0;int sum=nums[0],minlen=n+1;while(r<n){while(sum<target&&r<n){if(++r<n) sum+=nums[r];}if(sum>=target){minlen=min(minlen,r-l+1);sum-=nums[l];l++;}else break;}return minlen<=n?minlen:0;}
};

相关文章:

前缀和部分题目

前缀和 前缀和指数组的前 N项之和&#xff0c;是个比较基础的算法 例题 面试题 17.05. 字母与数字 给定一个放有字母和数字的数组&#xff0c;找到最长的子数组&#xff0c;且包含的字母和数字的个数相同。 返回该子数组&#xff0c;若存在多个最长子数组&#xff0c;返回左…...

三天吃透MySQL面试八股文

本文已经收录到Github仓库&#xff0c;该仓库包含计算机基础、Java基础、多线程、JVM、数据库、Redis、Spring、Mybatis、SpringMVC、SpringBoot、分布式、微服务、设计模式、架构、校招社招分享等核心知识点&#xff0c;欢迎star~ Github地址&#xff1a;https://github.com/…...

Giving You A guide to learning any topic faster than 95% of people

A guide to learning any topic faster than 95% of people: Richard Feynman was a physician who won the Nobel Prize in 1965. But he became known for his great lectures. Why? He was able to explain complex concepts in simple terms with these 4 steps: 1 • E…...

(七十七)大白话MySQL是如何根据成本优化选择执行计划的?(中)

上次我们讲完了全表扫描的成本计算方法&#xff0c;相信大家应该都理解了&#xff0c;其实还是比较简单的&#xff0c;今天我们来讲一下索引的成本计算方法&#xff0c;因为除了全表扫描之外&#xff0c;还可能多个索引都可以使用&#xff0c;但是当然同时一般只能用一个索引&a…...

原来CSS 也可以节流啊

Ⅰ、前言 「节流」 是为了减少请求的触发频率&#xff0c;不让用户点的太快&#xff0c;达到节省资源的目的 &#xff1b;通常 我们采用 JS 的 定时器 setTimeout &#xff0c;来控制点击多少秒才能在触发&#xff1b;其实 通过 CSS 也能达到 「节流」 的目的&#xff0c;下面…...

UE官方教程笔记03-功能、术语、操作简介

对官方教程视频[官方培训]03-UE功能、术语、操作简介 | 徐良安 Epic的笔记这一部分基本都是走马观花的简单介绍功能世界创建建模Mesh editingtool是一个全新的建模工具&#xff0c;具备大多数的主流建模软件的核心功能HOUDINI ENGINE FOR UNREALHoudini编辑器&#xff0c;可以用…...

BN,LN,IN,GN的理解和用法

绿色区域表示将该区域作用域(四种方法都贯穿了w,h维度)&#xff0c;即将该区域数值进行归一化&#xff0c;变为均值为0&#xff0c;标准差为1。BN的作用区域时N,W,H,表示一个batch数据的每一个通道均值为0&#xff0c;标准差为1&#xff1b;LN则是让每个数据的所有channel的均值…...

Linux:epoll模式web服务器代码,代码debug

源码&#xff1a; https://blog.csdn.net/weixin_44718794/article/details/107206136 修改的地方&#xff1a; 修改后代码&#xff1a; #include <stdio.h> #include <unistd.h> #include <stdlib.h> //#include “epoll_server.h” #ifndef _EPOLL_SER…...

SpringSecurity学习(四)密码加密、RememberMe记住我

文章目录密码加密一、简介密码为什么要加密常见的加密解决方案PasswordEncoder详解DelegatingPasswordEncoder二、自定义加密方式1. 使用灵活的密码加密方案&#xff08;BCryptPasswordEncoder&#xff09;加密验证&#xff08;推荐&#xff09;需要在密码前指定加密类型{bcryp…...

vue专项练习

一、循环实现一个列表的展示及删除功能 1.1 列表展示 1、背景&#xff1a; 完成一个这样的列表展示。使用v-for 循环功能 id接口名称测试人员项目名项目ID描述信息创建时间用例数1首页喵酱发财项目a1case的描述信息2019/11/6 14:50:30102个人中心张三发财项目a1case的描述信…...

【笔试题】百度+美团

发工资 链接&#xff1a;https://www.nowcoder.com/questionTerminal/e47cffeef25d43e3b16c11c9b28ac7e8 来源&#xff1a;牛客网 小度新聘请了一名员工牛牛, 每个月小度需要给牛牛至少发放m元工资(给牛牛发放的工资可以等于m元或者大于m元, 不能低于m)。 小度有一些钞票资金…...

【8.索引篇】

索引分类 索引和数据就是位于存储引擎中&#xff1a; 按「数据结构」分类&#xff1a;Btree索引、Hash索引、Full-text索引。按「物理存储」分类&#xff1a;聚簇索引&#xff08;主键索引&#xff09;、二级索引&#xff08;辅助索引&#xff09;。按「字段特性」分类&#…...

MySQL InnoDB存储引擎锁与事务实现原理解析(未完成)

InnoDB MySQL存储引擎是基于表的&#xff0c;也就是说每张表可以选择不同的存储引擎。 InnoDB存储引擎的表是索引组织的&#xff0c;也就是数据即索引。 存储引擎文件 InnoDB引擎会包含RedoLog重做日志文件和TableSpace表空间文件。 表空间文件 默认表空间文件&#xff08…...

P1683 入门(洛谷)JAVA

题目描述&#xff1a; 不是任何人都可以进入桃花岛的&#xff0c;黄药师最讨厌像郭靖一样呆头呆脑的人。所以&#xff0c;他在桃花岛的唯一入口处修了一条小路&#xff0c;这条小路全部用正方形瓷砖铺设而成。有的瓷砖可以踩&#xff0c;我们认为是安全的&#xff0c;而有的瓷砖…...

yocto编译烧录和脚本解析

提示&#xff1a;文章写完后&#xff0c;目录可以自动生成&#xff0c;如何生成可参考右边的帮助文档 文章目录前言一、初始化构建目录二、imx-setup-release.sh脚本解析三、编译单独编译内核四、烧录总结前言 本篇文章主要讲解如何在下载好源码之后进行编译和yocto的脚本解析…...

Proteus 8.15安装包安装教程

Proteus介绍Proteus的介绍Proteus8.15安装包Proteus8.15安装教程Proteus的介绍 Proteus是英国著名的EDA工具(仿真软件)&#xff0c;从原理图布图、代码调试到单片机与外围电路协同仿真&#xff0c;一键切换到PCB设计&#xff0c;真正实现了从概念到产品的完整设计。是世界上唯…...

Spring——AOP工作流程

AOP就是代理模式的开发简化 1.Spring容器启动 因为AOP是要将通知类作为一个bean对象交给spring进行管理的&#xff0c;还有经过通知类被增强的类。 此时还没有创建bean对象 2.读取所有切面配置中的切入点 在下面这段代码中&#xff0c;定义了两个切入点&#xff0c;但是只…...

c++11多线程之condition_variable、wait()、notify_one()、notify_all()的使用。

系列文章目录 文章目录系列文章目录前言一、基本概念1.1 std::condition_variable1.2 wait()函数1.2.1 wait()带第二个参数1.2.2 wait()不带第二个参数1.2.3 当其他线程用notify_one()或notify_all&#xff08;&#xff09;1.3 notify函数二、代码实例总结前言 C11多线程&…...

skywalking扩展实现 —— 监控数据的动态上报

把标题名整高大上一些&#xff0c;来掩盖需求的奇葩。 0. 目录1. 需求背景2. 需求描述3. 优势4. 实现4.1 扩展点4.2 配置项5. 优化6. 提醒7. 补充 - 关于微服务8. 参考1. 需求背景 过去一段时间&#xff0c;接手了一个迭代了数年的"基于微服务架构"搭建的产品。 自…...

【GoF 23】23种设计模式与OOP七大原则概述

1. 什么是GoF 23&#xff1f; GoF 23也就是23种设计模式。1995年GoF&#xff08;Gang of Four&#xff0c;四人组/四人帮&#xff09;合作出版了《设计模式&#xff1a;可复用面向对象软件的基础》一书&#xff0c;一共收录了23种设计模式&#xff0c;从此梳理了软件设计模式领…...

SCAU期末笔记 - 数据分析与数据挖掘题库解析

这门怎么题库答案不全啊日 来简单学一下子来 一、选择题&#xff08;可多选&#xff09; 将原始数据进行集成、变换、维度规约、数值规约是在以下哪个步骤的任务?(C) A. 频繁模式挖掘 B.分类和预测 C.数据预处理 D.数据流挖掘 A. 频繁模式挖掘&#xff1a;专注于发现数据中…...

【JVM】- 内存结构

引言 JVM&#xff1a;Java Virtual Machine 定义&#xff1a;Java虚拟机&#xff0c;Java二进制字节码的运行环境好处&#xff1a; 一次编写&#xff0c;到处运行自动内存管理&#xff0c;垃圾回收的功能数组下标越界检查&#xff08;会抛异常&#xff0c;不会覆盖到其他代码…...

【Oracle】分区表

个人主页&#xff1a;Guiat 归属专栏&#xff1a;Oracle 文章目录 1. 分区表基础概述1.1 分区表的概念与优势1.2 分区类型概览1.3 分区表的工作原理 2. 范围分区 (RANGE Partitioning)2.1 基础范围分区2.1.1 按日期范围分区2.1.2 按数值范围分区 2.2 间隔分区 (INTERVAL Partit…...

springboot整合VUE之在线教育管理系统简介

可以学习到的技能 学会常用技术栈的使用 独立开发项目 学会前端的开发流程 学会后端的开发流程 学会数据库的设计 学会前后端接口调用方式 学会多模块之间的关联 学会数据的处理 适用人群 在校学生&#xff0c;小白用户&#xff0c;想学习知识的 有点基础&#xff0c;想要通过项…...

CSS | transition 和 transform的用处和区别

省流总结&#xff1a; transform用于变换/变形&#xff0c;transition是动画控制器 transform 用来对元素进行变形&#xff0c;常见的操作如下&#xff0c;它是立即生效的样式变形属性。 旋转 rotate(角度deg)、平移 translateX(像素px)、缩放 scale(倍数)、倾斜 skewX(角度…...

Ubuntu系统多网卡多相机IP设置方法

目录 1、硬件情况 2、如何设置网卡和相机IP 2.1 万兆网卡连接交换机&#xff0c;交换机再连相机 2.1.1 网卡设置 2.1.2 相机设置 2.3 万兆网卡直连相机 1、硬件情况 2个网卡n个相机 电脑系统信息&#xff0c;系统版本&#xff1a;Ubuntu22.04.5 LTS&#xff1b;内核版本…...

DiscuzX3.5发帖json api

参考文章&#xff1a;PHP实现独立Discuz站外发帖(直连操作数据库)_discuz 发帖api-CSDN博客 简单改造了一下&#xff0c;适配我自己的需求 有一个站点存在多个采集站&#xff0c;我想通过主站拿标题&#xff0c;采集站拿内容 使用到的sql如下 CREATE TABLE pre_forum_post_…...

多元隐函数 偏导公式

我们来推导隐函数 z z ( x , y ) z z(x, y) zz(x,y) 的偏导公式&#xff0c;给定一个隐函数关系&#xff1a; F ( x , y , z ( x , y ) ) 0 F(x, y, z(x, y)) 0 F(x,y,z(x,y))0 &#x1f9e0; 目标&#xff1a; 求 ∂ z ∂ x \frac{\partial z}{\partial x} ∂x∂z​、 …...

Vue3 PC端 UI组件库我更推荐Naive UI

一、Vue3生态现状与UI库选择的重要性 随着Vue3的稳定发布和Composition API的广泛采用&#xff0c;前端开发者面临着UI组件库的重新选择。一个好的UI库不仅能提升开发效率&#xff0c;还能确保项目的长期可维护性。本文将对比三大主流Vue3 UI库&#xff08;Naive UI、Element …...

链式法则中 复合函数的推导路径 多变量“信息传递路径”

非常好&#xff0c;我们将之前关于偏导数链式法则中不能“约掉”偏导符号的问题&#xff0c;统一使用 二重复合函数&#xff1a; z f ( u ( x , y ) , v ( x , y ) ) \boxed{z f(u(x,y),\ v(x,y))} zf(u(x,y), v(x,y))​ 来全面说明。我们会展示其全微分形式&#xff08;偏导…...