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

leetcode303. 区域和检索 - 数组不可变(java)

前缀和数组的应用

  • 区域和检索 - 数组不可变
    • 题目描述
    • 前缀和数组
    • 代码演示

区域和检索 - 数组不可变

难度 - 简单
原题链接 - 区域和检索 - 数组不可变

题目描述

给定一个整数数组 nums,处理以下类型的多个查询:
计算索引 left 和 right (包含 left 和 right)之间的 nums 元素的 和 ,其中 left <= right
实现 NumArray 类:
NumArray(int[] nums) 使用数组 nums 初始化对象
int sumRange(int i, int j) 返回数组 nums 中索引 left 和 right 之间的元素的 总和 ,包含 left 和 right 两点(也就是 nums[left] + nums[left + 1] + … + nums[right] )

示例 1:
输入:
[“NumArray”, “sumRange”, “sumRange”, “sumRange”]
[[[-2, 0, 3, -5, 2, -1]], [0, 2], [2, 5], [0, 5]]
输出:
[null, 1, -1, -3]
解释:
NumArray numArray = new NumArray([-2, 0, 3, -5, 2, -1]);
numArray.sumRange(0, 2); // return 1 ((-2) + 0 + 3)
numArray.sumRange(2, 5); // return -1 (3 + (-5) + 2 + (-1))
numArray.sumRange(0, 5); // return -3 ((-2) + 0 + 3 + (-5) + 2 + (-1))

提示:
1 <= nums.length <= 1e4
-105 <= nums[i] <= 1e5
0 <= i <= j < nums.length
最多调用 104 次 sumRange 方法
在这里插入图片描述

前缀和数组

核心思路是我们 new 一个新的数组 preSum 出来,preSum[i] 记录 nums[0…i-1] 的累加和,看图 10 = 3 + 5 + 2:
在这里插入图片描述
看这个 preSum 数组,如果我想求索引区间 [1, 4] 内的所有元素之和,就可以通过 preSum[5] - preSum[1] 得出。

:这样,sumRange 函数仅仅需要做一次减法运算,避免了每次进行 for 循环调用,最坏时间复杂度为常数 O(1)。
这个技巧在生活中运用也挺广泛的,比方说,你们班上有若干同学,每个同学有一个期末考试的成绩(满分 100 分),那么请你实现一个 API,输入任意一个分数段,返回有多少同学的成绩在这个分数段内。

代码演示

class NumArray {private int[]preSum;public NumArray(int[] nums) {preSum = new int[nums.length];preSum[0] = nums[0];for(int i = 1; i < nums.length;i++){preSum[i] = preSum[i - 1] + nums[i];}}public int sumRange(int left, int right) {  return left != 0 ? preSum[right] - preSum[left - 1] : preSum[right] ;}
}

相关文章:

leetcode303. 区域和检索 - 数组不可变(java)

前缀和数组的应用 区域和检索 - 数组不可变题目描述前缀和数组代码演示 区域和检索 - 数组不可变 难度 - 简单 原题链接 - 区域和检索 - 数组不可变 题目描述 给定一个整数数组 nums&#xff0c;处理以下类型的多个查询: 计算索引 left 和 right &#xff08;包含 left 和 righ…...

PHP 安装Composer,vue前端依赖包

电脑安装Composer 官网下载&#xff1a;https://getcomposer.org/Composer-Setup.exe 后端安装&#xff1a; 检查是否安装依赖&#xff1a; 安装Composer install 或 Composer i 前端安装&#xff1a; yarn install 安装依赖...

OpenCV项目开发实战--基于Python/C++实现鼠标注释图像和轨迹栏来控制图像大小

鼠标指针是图形用户界面 (GUI) 中的关键组件。没有它,您就无法真正考虑与 GUI 进行交互。那么,让我们深入了解 OpenCV 中鼠标和轨迹栏的内置函数。我们将演示如何使用鼠标来注释图像,以及如何使用轨迹栏来控制图像的大小 我们将使用下图来演示 OpenCV 中鼠标指针和轨迹栏功能…...

❤ Vue使用Eslint检测报错问题和解决

❤ Vue使用Eslint检测报错问题和解决 1、 关闭Eslint检测 关闭ESLint语法检测即可&#xff1a;具体步骤如下&#xff1a; 第一步我们打开setting设置&#xff1a; 打开左上角的file&#xff0c;然后点击setting 接下来进入setting以后我们来看下面操作&#xff1a; eol-l…...

解决运行在微信小程序中报[ app.json 文件内容错误] app.json: app.json 未找到(env: Windows,mp,1.05.2204

找到project.config.json文件夹 添加 "miniprogramRoot": "unpackage/dist/dev/mp-weixin/", 即可...

python 基础 -- 安装Python模块

作为一个流行的开源开发项目&#xff0c;Python拥有一个由贡献者和用户组成的活跃支持社区&#xff0c;他们还根据开源许可条款向其他Python开发人员提供他们的软件。 这允许Python用户有效地共享和协作&#xff0c;从其他人已经创建的常见(有时甚至是罕见的!)问题的解决方案中…...

C语言实现状态机

关于状态机&#xff0c;基础的知识点可以自行理解&#xff0c;讲解的很多&#xff0c;这里主要是想写一个有限状态机FSM通用的写法&#xff0c;目的在于更好理解&#xff0c;移植&#xff0c;节省代码阅读与调试时间&#xff0c;体现出编程之美。 传统的实现方案 if...else : …...

交叉编译工具链arm-linux-gnueabihf的安装-ubuntu 20.04

前面下载安装步骤参考该博主的文章 http://t.csdn.cn/ZbjFX 另&#xff1a;本人对所遇到的环境变量的配置问题作补充 1.修改环境变量 建议直接在.bashrc文件作修改 &#xff0c;修改方式相同 ( vi :视自己的编辑器而定) sudo vi ~/.bashrc 2.修改环境变量后&#xff0c;可…...

Java的类加载器

类加载 1、ClassLoader 用来加载 Class 文件 2、 系统内置的ClassLoader 通过双亲委托加载指定目录下的class和资源 3、 可以自定义ClassLoader 一般覆盖findClass() 4、ContextClassLoader 与线程相关&#xff0c;可以获取和设置&#xff0c;可以绕过双亲委托的机制。 三个类…...

Stable Diffusion web UI 部署详细教程

前言 本文使用 AutoDL 平台进行 Stable Diffusion web UI 云端部署 AutoDL 官网&#xff1a;AutoDL算力云 | 弹性、好用、省钱。租GPU就上AutoDL Stable Diffusion web UI 官网&#xff1a;AUTOMATIC1111/stable-diffusion-webui: Stable Diffusion web UI (github.com) 步…...

《深度学习计算机视觉 》书籍分享(包邮送书三本)

深度学习计算机视觉介绍 随着计算机技术的发展和进步&#xff0c;计算机视觉领域得到了广泛的关注和研究。而深度学习作为一种强大的机器学习方法&#xff0c;已经成为计算机视觉领域的重要工具之一。本文将介绍深度学习在计算机视觉中的应用和取得的成果。 深度学习是一种模…...

【使用 k 折叠交叉验证的卷积神经网络(CNN)】基于卷积神经网络的无特征EMG模式识别研究(Matlab代码实现)

&#x1f4a5;&#x1f4a5;&#x1f49e;&#x1f49e;欢迎来到本博客❤️❤️&#x1f4a5;&#x1f4a5; &#x1f3c6;博主优势&#xff1a;&#x1f31e;&#x1f31e;&#x1f31e;博客内容尽量做到思维缜密&#xff0c;逻辑清晰&#xff0c;为了方便读者。 ⛳️座右铭&a…...

微服务 Nacos配置热部署

在nacos中添加配置文件 在配置列表中添加配置&#xff0c; 注意&#xff1a;项目的核心配置&#xff0c;需要热更新的配置才有放到nacos管理的必要。基本不会变更的一些配置还是保存在微服务本地比较好。 从微服务拉取配置 微服务要拉取nacos中管理的配置&#xff0c;并且与…...

国产调度器之光——Fsched到底有多能打?

这是一篇推荐我们速石自研调度器——Fsched的文章。 看起来在专门写调度器&#xff0c;但又不完全在写。 往下看&#xff0c;你就懂了。 本篇一共五个章节&#xff1a; 一、介绍一下主角——速石自研调度器Fsched 二、只要有个调度器&#xff0c;就够了吗&#xff1f; 三…...

LeetCode:53. 最大子数组和 - Python

53. 最大子数组和 问题描述&#xff1a; 给你一个整数数组 nums &#xff0c;请你找出一个具有最大和的连续子数组&#xff08;子数组最少包含一个元素&#xff09;&#xff0c;返回其最大和。 子数组 是数组中的一个连续部分。 示例 1&#xff1a; 输入&#xff1a;nums [-…...

网站建设 之 react usestate

react着重在于“不可变动” 如果变动了怎么办呢&#xff1f;那就整个新的 局部变量/函数/jsx-》state/props-〉ref&#xff0c;依次越来越难变 每次state/props&#xff0c;局部变量/函数/jsx都是新的 既然函数是新的&#xff0c;那么就会有一个问题&#xff0c;回调函数用…...

第一讲使用IDEA创建Java工程——HelloWorld

一、前言导读 为了能够让初学者更快上手Java,不会像其他书籍或者视频一样,介绍一大堆历史背景,默认大家已经知道Java这么编程语言了。本专栏只会讲解干货,直接从HelloWord入手,慢慢由浅入深,讲个各个知识点,这些知识点也是目前工作中项目使用的,而不是讲一些老的知识点…...

BootstrapBlazor组件使用:数据注解

文章目录 前言BB数据注解数据注解源码数据注解简介注解简单实例[BB 编辑弹窗](https://www.blazor.zone/edit-dialog)[ValidateForm 表单组件](https://www.blazor.zone/validate-form)使用简介 前言 BootstrapBlazor(一下简称BB)是个特别好用的组件&#xff0c;基本上满足了大…...

MySQL 触发器

文章目录 1.简介2.行级与语句级触发器3.触发时机4.触发器优缺点5.创建触发器语法示例 6.查看触发器7.删除触发器参考文献 1.简介 触发器&#xff08;Trigger&#xff09;是与表关联的命名数据库对象&#xff0c;当表发生特定事件时激活。 触发器的一些用途是对要插入表中的值执…...

DPDK主从进程模式 rte_mempool_put失败

版本&#xff1a;19.11.6 情景&#xff1a;主进程应用rte_mempool_create创建mempool&#xff0c;rte_mempool_get获取数据&#xff1b;从进程应用rte_mempool_put归还数据 问题&#xff1a;从进程rte_mempool_put无法归还数据 原因&#xff1a;DPDK通过rte_mempool_ops_tab…...

浏览器访问 AWS ECS 上部署的 Docker 容器(监听 80 端口)

✅ 一、ECS 服务配置 Dockerfile 确保监听 80 端口 EXPOSE 80 CMD ["nginx", "-g", "daemon off;"]或 EXPOSE 80 CMD ["python3", "-m", "http.server", "80"]任务定义&#xff08;Task Definition&…...

《从零掌握MIPI CSI-2: 协议精解与FPGA摄像头开发实战》-- CSI-2 协议详细解析 (一)

CSI-2 协议详细解析 (一&#xff09; 1. CSI-2层定义&#xff08;CSI-2 Layer Definitions&#xff09; 分层结构 &#xff1a;CSI-2协议分为6层&#xff1a; 物理层&#xff08;PHY Layer&#xff09; &#xff1a; 定义电气特性、时钟机制和传输介质&#xff08;导线&#…...

visual studio 2022更改主题为深色

visual studio 2022更改主题为深色 点击visual studio 上方的 工具-> 选项 在选项窗口中&#xff0c;选择 环境 -> 常规 &#xff0c;将其中的颜色主题改成深色 点击确定&#xff0c;更改完成...

【Redis技术进阶之路】「原理分析系列开篇」分析客户端和服务端网络诵信交互实现(服务端执行命令请求的过程 - 初始化服务器)

服务端执行命令请求的过程 【专栏简介】【技术大纲】【专栏目标】【目标人群】1. Redis爱好者与社区成员2. 后端开发和系统架构师3. 计算机专业的本科生及研究生 初始化服务器1. 初始化服务器状态结构初始化RedisServer变量 2. 加载相关系统配置和用户配置参数定制化配置参数案…...

mysql已经安装,但是通过rpm -q 没有找mysql相关的已安装包

文章目录 现象&#xff1a;mysql已经安装&#xff0c;但是通过rpm -q 没有找mysql相关的已安装包遇到 rpm 命令找不到已经安装的 MySQL 包时&#xff0c;可能是因为以下几个原因&#xff1a;1.MySQL 不是通过 RPM 包安装的2.RPM 数据库损坏3.使用了不同的包名或路径4.使用其他包…...

听写流程自动化实践,轻量级教育辅助

随着智能教育工具的发展&#xff0c;越来越多的传统学习方式正在被数字化、自动化所优化。听写作为语文、英语等学科中重要的基础训练形式&#xff0c;也迎来了更高效的解决方案。 这是一款轻量但功能强大的听写辅助工具。它是基于本地词库与可选在线语音引擎构建&#xff0c;…...

云原生玩法三问:构建自定义开发环境

云原生玩法三问&#xff1a;构建自定义开发环境 引言 临时运维一个古董项目&#xff0c;无文档&#xff0c;无环境&#xff0c;无交接人&#xff0c;俗称三无。 运行设备的环境老&#xff0c;本地环境版本高&#xff0c;ssh不过去。正好最近对 腾讯出品的云原生 cnb 感兴趣&…...

毫米波雷达基础理论(3D+4D)

3D、4D毫米波雷达基础知识及厂商选型 PreView : https://mp.weixin.qq.com/s/bQkju4r6med7I3TBGJI_bQ 1. FMCW毫米波雷达基础知识 主要参考博文&#xff1a; 一文入门汽车毫米波雷达基本原理 &#xff1a;https://mp.weixin.qq.com/s/_EN7A5lKcz2Eh8dLnjE19w 毫米波雷达基础…...

TSN交换机正在重构工业网络,PROFINET和EtherCAT会被取代吗?

在工业自动化持续演进的今天&#xff0c;通信网络的角色正变得愈发关键。 2025年6月6日&#xff0c;为期三天的华南国际工业博览会在深圳国际会展中心&#xff08;宝安&#xff09;圆满落幕。作为国内工业通信领域的技术型企业&#xff0c;光路科技&#xff08;Fiberroad&…...

消防一体化安全管控平台:构建消防“一张图”和APP统一管理

在城市的某个角落&#xff0c;一场突如其来的火灾打破了平静。熊熊烈火迅速蔓延&#xff0c;滚滚浓烟弥漫开来&#xff0c;周围群众的生命财产安全受到严重威胁。就在这千钧一发之际&#xff0c;消防救援队伍迅速行动&#xff0c;而豪越科技消防一体化安全管控平台构建的消防“…...