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

303. 区域和检索 - 数组不可变

303. 区域和检索 - 数组不可变

给定一个整数数组 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<=1041 <= nums.length <= 10^41<=nums.length<=104
  • −105<=nums[i]<=105-10^5 <= nums[i] <= 10^5105<=nums[i]<=105
  • 0<=i<=j<nums.length0 <= i <= j < nums.length0<=i<=j<nums.length
  • 最多调用 10410^4104 次 sumRange 方法

思路:(前缀和)

根据数学层面可以这样理解:
在这里插入图片描述
代码理解: 前缀和数组 sums[i]里面存的就是原数组num的前 i 项和,例如sums[2] 这里面存的就是原数组num的前2项和

而数组最大的优点就是便于可以直接根据索引查找,前缀和就是充分运用了数组这个优点,只要理解了前缀和这个概念,代码的思路其实很简单 思路:
1、首先创建一个前缀和数组int []sums

2、由于前缀和数组sums[]里面存的是原数组num的前i项和,故使用其构造方法创建前缀数组sums[]时,要引入原数组num[]

3、注意创建sums[]数组时要注意,数组长度比数组要大一个数组空间,方便数组查询

4、创建完毕后,就直接根据传过来的right和left来对前缀和数组进行查找,注意查找right时注意加一,防止数组下标越界 , 5、查找到之后,再让两个查找到的数进行相减

6、相减之后的数就返回其值

代码:(Java)

public class NumArray {public int[] sums;public NumArray(int[] nums) {sums = new int[nums.length + 1];sums[0] = 0;for(int i = 1; i <= nums.length ; i++) {sums[i] = sums[i - 1] + nums[i - 1];}}public int sumRange(int left, int right) {return sums[right+1] - sums[left];}}
public class Demo {public static void main(String[] args) {// TODO Auto-generated method stubint numbers [][] = {{-2, 0, 3, -5, 2, -1}, {0, 2}, {2, 5}, {0, 5}};int sums[] = new int[numbers.length - 1];NumArray numary  = new NumArray(numbers[0]);for(int i = 1; i < numbers.length; i++) {sums[i-1] = numary.sumRange(numbers[i][0], numbers[i][1]);System.out.print(sums[i - 1] + " ");}	}
}

复杂度分析:

  • 时间复杂度:初始化 O(n),每次检索 O(1),其中 n 是数组 nums的长度。 初始化需要遍历数组 nums 计算前缀和,时间复杂度是 O(n)。 每次检索只需要得到两个下标处的前缀和,然后计算差值,时间复杂度是 O(1)。

  • 空间复杂度:O(n),其中 n 是数组 nums 的长度。需要创建一个长度为 n+1的前缀和数组。

注:仅供学习参考!

题目来源:力扣。

相关文章:

303. 区域和检索 - 数组不可变

303. 区域和检索 - 数组不可变 给定一个整数数组 nums&#xff0c;处理以下类型的多个查询: 计算索引 left 和 right &#xff08;包含 left 和 right&#xff09;之间的 nums 元素的 和 &#xff0c;其中 left < right 实现 NumArray 类&#xff1a; NumArray(int[] num…...

Spring Cloud融合Nacos配置加载优先级 | Spring Cloud 8

一、前言 Spring Cloud Alibaba Nacos Config 目前提供了三种配置能力从 Nacos 拉取相关的配置&#xff1a; A&#xff1a;通过内部相关规则(应用名、扩展名、profiles)自动生成相关的 Data Id 配置B&#xff1a;通过 spring.cloud.nacos.config.extension-configs的方式支持…...

LeetCode 236.二叉树的最近公共祖先

给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。百度百科中最近公共祖先的定义为&#xff1a;“对于有根树 T 的两个节点 p、q&#xff0c;最近公共祖先表示为一个节点 x&#xff0c;满足 x 是 p、q 的祖先且 x 的深度尽可能大&#xff08;一个节点也可以是它自己的祖…...

awk简单实例(持续更新中)

一 概述 awk命令是一种分析和处理文本文件的编程工具。它的功能非常强大&#xff0c;是Linux/Unix系统中最常用的过滤工具。 awk内建变量&#xff1a; NF 整个数据行(即$0)拥有的字段总数 NR 当前awk所处理的数据行的编号 $0 当前awk所处理的数据行 $1 数据行的第1个字段 $2 数…...

react动态路由组件的封装

react动态路由组件的封装 我这篇比较全面 首先下载包 npm i react-router-dom5 这里为什么要用5的版本为啥不用最新的&#xff0c;原因在于老版本跟新版本写法不一样 老版本 import { HashRouter, Route, Switch, Redirect } from react-router-dom;render() {return (<Ha…...

Vue项目中引入高德地图步骤详解

高德地图API官网&#xff1a;高德开放平台 | 高德地图API。 目录 一、案例效果 二、开发准备 1. 注册高德开放平台账号 2. 创建应用添加 key 值 三、项目中使用地图组件 1. npm 获取高德地图 API 2.在项目中新建 MapContainer.vue 文件&#xff0c;用作地图组件。 3.在…...

软件测试用例篇(2)

功能测试界面测试兼容性测试安全测试易用性测试性能测试 针对有需求的案例来设计测试用例:邮箱注册&#xff0c;部分测试用例 https://zay1xofb7z6.feishu.cn/mindnotes/bmncnKD5Ak6GSZl3PRlWDgF9z3g#mindmap 一)等价类: 场景需求:姓名长度是6-200位&#xff0c;那么如何进行设…...

leetcode题解-27. Remove Element

给你一个数组 nums 和一个值 val&#xff0c;你需要 原地 移除所有数值等于 val 的元素&#xff0c;并返回移除后数组的新长度。 不要使用额外的数组空间&#xff0c;你必须仅使用 O(1) 额外空间并 原地 修改输入数组。 元素的顺序可以改变。你不需要考虑数组中超出新长度后面…...

【fly-iot飞凡物联】(4):在linux系统上搭建arduino环境,可以使用离线包,导入到arduino上即可。

目录前言1&#xff0c;关于2&#xff0c;然后就可以找到ESP32&#xff0c;ESP8266的主版3&#xff0c;方法2&#xff0c;github下载&#xff0c;然后手动添加到ide中吧4&#xff0c;总结前言 本文的原文连接是: https://blog.csdn.net/freewebsys/article/details/108971807 未…...

java实例解析类图中【关联、组合和聚合】的区别

总目录链接==>> AutoSAR入门和实战系列总目录 文章目录 聚合Composition聚合与组合的区别关联是两个独立类之间的关系,它通过它们的对象建立关联。关联可以是一对一、一对多、多对一、多对多。在面向对象的编程中,一个对象与另一个对象通信以使用该对象提供的功能和服…...

基于m-p条件查询代码生成

目录 起因 演示 使用 0.自定义注解 1.定义一个dto的条件查询类 2.调用主程序 效果图 小结 代码 注解 Dto类 完整代码 起因 最近两天一直写后台管理统计的增删改查(很少写增删改查&#xff0c;所以不是很熟练)&#xff0c;几乎每个表都要涉及到条件查询的业务&#xf…...

【LeetCode】带环链表两道题

第一题&#xff1a;环形链表 问题介绍 给你一个链表的头节点head &#xff0c;判断链表中是否有环。 如果链表中有某个节点&#xff0c;可以通过连续跟踪next指针再次到达&#xff0c;则链表中存在环。为了表示给定链表中的环&#xff0c;评测系统内部使用整数pos 来表示链表…...

CSS奇思妙想之-利用CSS裁剪(clip-path)完成各种图形

在日常开发当中&#xff0c;如果想要开发多边形&#xff0c;一般都需要多个盒子或者伪元素的帮助&#xff0c;有没有一直办法能只使用一个盒子实现呢&#xff1f; 有的&#xff1a;css裁剪 clip-path介绍 css裁剪&#xff08;clip-path&#xff09;这个属性平时率非常低。但是…...

力扣每日一题刷题总结:哈希表篇

剑指 Offer II 033.变位词组 Medium 哈希表 变位词 2023/3/3 给定一个字符串数组 strs &#xff0c;将 变位词 组合在一起。 可以按任意顺序返回结果列表。 注意&#xff1a;若两个字符串中每个字符出现的次数都相同&#xff0c;则称它们互为变位词。 示例&#xff1a; 示例 1:…...

【Redis】redis大key和大value的危害,如何处理?

前序 还记得上次和同事一起去面试候选人时&#xff0c;同事提了一个问题&#xff1a;Redis的大key有什么危害&#xff1f;当时候选人主要作答的角度是一个key的value较大时的情况&#xff0c;比如&#xff1a; 内存不均&#xff1a;单value较大时&#xff0c;可能会导致节点之…...

Spring Boot:实现MyBatis动态创建表

在有些应用场景中&#xff0c;我们会有需要动态创建和操作表的需求。 比如因为单表数据存储量太大而采取分表存储的情况&#xff0c;又或者是按日期生成日志表存储系统日志等等。这个时候就需要我们动态的生成和操作数据库表了。 而我们都知道&#xff0c;以往我们使用MyBati…...

SpringBoot+Seata在多数据源和feign中的简单使用

SpringBootSeata简单使用 目录seata执行过程安装seata下载seata使用自定义配置文件,NACOS为注册中心结合springboot实现AT模式1.多数据源引入依赖bootstrap.yml配置在使用的方法上用GlobalTransactional注解调用接口正常时调用接口报错时回滚2.配合feignseata优缺点seata执行过…...

计算机网络中的原码、反码、补码

写在前面 原码、反码、补码是计算机组成原理中的概念&#xff0c;是计算机网络的基础知识之一。这些概念是为了处理二进制数的符号位而引入的&#xff0c;常用于计算机中的整数运算&#xff0c;也常用于数据存储和传输等领域。因此&#xff0c;了解和掌握这些概念对于理解计算机…...

七、Bean的实例化方式

Spring为Bean提供了多种实例化方式&#xff0c;通常包括4种方式。&#xff08;也就是说在Spring中为Bean对象的创建准备了多种方案&#xff0c;目的是&#xff1a;更加灵活&#xff09; 第一种&#xff1a;通过构造方法实例化第二种&#xff1a;通过简单工厂模式实例化第三种&…...

Windows程序员学习Linux环境下VI(VIM)编辑器的使用方法

我是荔园微风&#xff0c;作为一名在IT界整整25年的老兵&#xff0c;今天我们来重新审视一下Windows程序员如何学习Linux环境知识。由于很多程序在Windows环境下开发好后&#xff0c;还要部署到Linux服务器上去&#xff0c;所以作为Windows程序员有必要学习Linux环境的知识。VI…...

内存分配函数malloc kmalloc vmalloc

内存分配函数malloc kmalloc vmalloc malloc实现步骤: 1)请求大小调整:首先,malloc 需要调整用户请求的大小,以适应内部数据结构(例如,可能需要存储额外的元数据)。通常,这包括对齐调整,确保分配的内存地址满足特定硬件要求(如对齐到8字节或16字节边界)。 2)空闲…...

ES6从入门到精通:前言

ES6简介 ES6&#xff08;ECMAScript 2015&#xff09;是JavaScript语言的重大更新&#xff0c;引入了许多新特性&#xff0c;包括语法糖、新数据类型、模块化支持等&#xff0c;显著提升了开发效率和代码可维护性。 核心知识点概览 变量声明 let 和 const 取代 var&#xf…...

day52 ResNet18 CBAM

在深度学习的旅程中&#xff0c;我们不断探索如何提升模型的性能。今天&#xff0c;我将分享我在 ResNet18 模型中插入 CBAM&#xff08;Convolutional Block Attention Module&#xff09;模块&#xff0c;并采用分阶段微调策略的实践过程。通过这个过程&#xff0c;我不仅提升…...

在HarmonyOS ArkTS ArkUI-X 5.0及以上版本中,手势开发全攻略:

在 HarmonyOS 应用开发中&#xff0c;手势交互是连接用户与设备的核心纽带。ArkTS 框架提供了丰富的手势处理能力&#xff0c;既支持点击、长按、拖拽等基础单一手势的精细控制&#xff0c;也能通过多种绑定策略解决父子组件的手势竞争问题。本文将结合官方开发文档&#xff0c…...

定时器任务——若依源码分析

分析util包下面的工具类schedule utils&#xff1a; ScheduleUtils 是若依中用于与 Quartz 框架交互的工具类&#xff0c;封装了定时任务的 创建、更新、暂停、删除等核心逻辑。 createScheduleJob createScheduleJob 用于将任务注册到 Quartz&#xff0c;先构建任务的 JobD…...

【C++从零实现Json-Rpc框架】第六弹 —— 服务端模块划分

一、项目背景回顾 前五弹完成了Json-Rpc协议解析、请求处理、客户端调用等基础模块搭建。 本弹重点聚焦于服务端的模块划分与架构设计&#xff0c;提升代码结构的可维护性与扩展性。 二、服务端模块设计目标 高内聚低耦合&#xff1a;各模块职责清晰&#xff0c;便于独立开发…...

RNN避坑指南:从数学推导到LSTM/GRU工业级部署实战流程

本文较长&#xff0c;建议点赞收藏&#xff0c;以免遗失。更多AI大模型应用开发学习视频及资料&#xff0c;尽在聚客AI学院。 本文全面剖析RNN核心原理&#xff0c;深入讲解梯度消失/爆炸问题&#xff0c;并通过LSTM/GRU结构实现解决方案&#xff0c;提供时间序列预测和文本生成…...

3-11单元格区域边界定位(End属性)学习笔记

返回一个Range 对象&#xff0c;只读。该对象代表包含源区域的区域上端下端左端右端的最后一个单元格。等同于按键 End 向上键(End(xlUp))、End向下键(End(xlDown))、End向左键(End(xlToLeft)End向右键(End(xlToRight)) 注意&#xff1a;它移动的位置必须是相连的有内容的单元格…...

Aspose.PDF 限制绕过方案:Java 字节码技术实战分享(仅供学习)

Aspose.PDF 限制绕过方案&#xff1a;Java 字节码技术实战分享&#xff08;仅供学习&#xff09; 一、Aspose.PDF 简介二、说明&#xff08;⚠️仅供学习与研究使用&#xff09;三、技术流程总览四、准备工作1. 下载 Jar 包2. Maven 项目依赖配置 五、字节码修改实现代码&#…...

短视频矩阵系统文案创作功能开发实践,定制化开发

在短视频行业迅猛发展的当下&#xff0c;企业和个人创作者为了扩大影响力、提升传播效果&#xff0c;纷纷采用短视频矩阵运营策略&#xff0c;同时管理多个平台、多个账号的内容发布。然而&#xff0c;频繁的文案创作需求让运营者疲于应对&#xff0c;如何高效产出高质量文案成…...