当前位置: 首页 > 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…...

Redis的发布订阅模式与专业的 MQ(如 Kafka, RabbitMQ)相比,优缺点是什么?适用于哪些场景?

Redis 的发布订阅&#xff08;Pub/Sub&#xff09;模式与专业的 MQ&#xff08;Message Queue&#xff09;如 Kafka、RabbitMQ 进行比较&#xff0c;核心的权衡点在于&#xff1a;简单与速度 vs. 可靠与功能。 下面我们详细展开对比。 Redis Pub/Sub 的核心特点 它是一个发后…...

Netty从入门到进阶(二)

二、Netty入门 1. 概述 1.1 Netty是什么 Netty is an asynchronous event-driven network application framework for rapid development of maintainable high performance protocol servers & clients. Netty是一个异步的、基于事件驱动的网络应用框架&#xff0c;用于…...

MySQL 知识小结(一)

一、my.cnf配置详解 我们知道安装MySQL有两种方式来安装咱们的MySQL数据库&#xff0c;分别是二进制安装编译数据库或者使用三方yum来进行安装,第三方yum的安装相对于二进制压缩包的安装更快捷&#xff0c;但是文件存放起来数据比较冗余&#xff0c;用二进制能够更好管理咱们M…...

MySQL JOIN 表过多的优化思路

当 MySQL 查询涉及大量表 JOIN 时&#xff0c;性能会显著下降。以下是优化思路和简易实现方法&#xff1a; 一、核心优化思路 减少 JOIN 数量 数据冗余&#xff1a;添加必要的冗余字段&#xff08;如订单表直接存储用户名&#xff09;合并表&#xff1a;将频繁关联的小表合并成…...

三分算法与DeepSeek辅助证明是单峰函数

前置 单峰函数有唯一的最大值&#xff0c;最大值左侧的数值严格单调递增&#xff0c;最大值右侧的数值严格单调递减。 单谷函数有唯一的最小值&#xff0c;最小值左侧的数值严格单调递减&#xff0c;最小值右侧的数值严格单调递增。 三分的本质 三分和二分一样都是通过不断缩…...

什么是VR全景技术

VR全景技术&#xff0c;全称为虚拟现实全景技术&#xff0c;是通过计算机图像模拟生成三维空间中的虚拟世界&#xff0c;使用户能够在该虚拟世界中进行全方位、无死角的观察和交互的技术。VR全景技术模拟人在真实空间中的视觉体验&#xff0c;结合图文、3D、音视频等多媒体元素…...

CppCon 2015 学习:Time Programming Fundamentals

Civil Time 公历时间 特点&#xff1a; 共 6 个字段&#xff1a; Year&#xff08;年&#xff09;Month&#xff08;月&#xff09;Day&#xff08;日&#xff09;Hour&#xff08;小时&#xff09;Minute&#xff08;分钟&#xff09;Second&#xff08;秒&#xff09; 表示…...

GAN模式奔溃的探讨论文综述(一)

简介 简介:今天带来一篇关于GAN的,对于模式奔溃的一个探讨的一个问题,帮助大家更好的解决训练中遇到的一个难题。 论文题目:An in-depth review and analysis of mode collapse in GAN 期刊:Machine Learning 链接:...

【1】跨越技术栈鸿沟:字节跳动开源TRAE AI编程IDE的实战体验

2024年初&#xff0c;人工智能编程工具领域发生了一次静默的变革。当字节跳动宣布退出其TRAE项目&#xff08;一款融合大型语言模型能力的云端AI编程IDE&#xff09;时&#xff0c;技术社区曾短暂叹息。然而这一退场并非终点——通过开源社区的接力&#xff0c;TRAE在WayToAGI等…...

【阅读笔记】MemOS: 大语言模型内存增强生成操作系统

核心速览 研究背景 ​​研究问题​​&#xff1a;这篇文章要解决的问题是当前大型语言模型&#xff08;LLMs&#xff09;在处理内存方面的局限性。LLMs虽然在语言感知和生成方面表现出色&#xff0c;但缺乏统一的、结构化的内存架构。现有的方法如检索增强生成&#xff08;RA…...