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

LeetCode——1590. 使数组和能被 P 整除

一、题目

给你一个正整数数组 nums,请你移除 最短 子数组(可以为 空),使得剩余元素的 和 能被 p 整除。 不允许 将整个数组都移除。

请你返回你需要移除的最短子数组的长度,如果无法满足题目要求,返回 -1 。

子数组 定义为原数组中连续的一组元素。
在这里插入图片描述
来源:力扣(LeetCode)
链接:https://leetcode.cn/problems/make-sum-divisible-by-p/description/

二、C++解法

我的思路及代码

我的方法时间复杂度太高,导致不能通过测试用例
采用前缀和的思路,然后从头开始用不同的窗口大小对数组进行遍历,窗口内的元素即为被删除的元素,直到最后剩下的数组元素和可以被整除返回当前的窗口大小,否则返回 -1。由于本题目只需要判断是否可以被整除,所以在前缀和中我们可以简化存储的数据,每次可以存储取余后的数据。

class Solution {
public:int minSubarray(vector<int>& nums, int p) {int size = nums.size();int prefixSum[size+1];int ans=1;prefixSum[0] = 0;for(int i=1;i<nums.size()+1;i++){prefixSum[i] = (prefixSum[i-1]+nums[i-1])%p;}if(prefixSum[size]%p==0)return 0;while(ans<size+1){for(int j=ans;j<size+1;j++){if((prefixSum[size]-(prefixSum[j]-prefixSum[j-ans]))%p==0)return ans;}ans++;}return -1;}
};
  • 时间复杂度:O(n2),其中 n 是数组 nums 的长度
  • 空间复杂度:O(n),数组需要 O(n) 的空间

官方参考代码

前缀和+哈希表

在这里插入图片描述

  • 时间复杂度:O(n),其中 n 是数组 nums 的长度。遍历数组 nums 需要 O(n) 的时间
  • 空间复杂度:O(n),保存哈希表需要 O(n) 的空间

相关文章:

LeetCode——1590. 使数组和能被 P 整除

一、题目 给你一个正整数数组 nums&#xff0c;请你移除 最短 子数组&#xff08;可以为 空&#xff09;&#xff0c;使得剩余元素的 和 能被 p 整除。 不允许 将整个数组都移除。 请你返回你需要移除的最短子数组的长度&#xff0c;如果无法满足题目要求&#xff0c;返回 -1…...

12N65-ASEMI高压MOS管12N65

编辑-Z 12N65在TO-220封装里的静态漏极源导通电阻&#xff08;RDS(ON)&#xff09;为0.68Ω&#xff0c;是一款N沟道高压MOS管。12N65的最大脉冲正向电流ISM为48A&#xff0c;零栅极电压漏极电流(IDSS)为10uA&#xff0c;其工作时耐温度范围为-55~150摄氏度。12N65功耗&#x…...

cushy-serial 一个轻量级Python serial库

本文自笔者博客: https://www.blog.zeeland.cn/archives/rgoihgxcoci3 简介 cushy-serial是一个轻量级的Serial框架&#xff0c;初衷是希望使Serial编程变得更加简单、快捷&#xff0c;因此&#xff0c;相较于传统的pyserial&#xff0c;该框架可以更加快速地构建起一个serial…...

音视频开发系列(7)——Opengl常用Api介绍part1

GLES20.glTexParameteri GLES20.glTexParameteri是OpenGL ES 2.0用于设置纹理过滤器和纹理包装模式的函数。它有三个参数&#xff1a; target参数 target参数指定要设置纹理参数的纹理目标&#xff0c;根据不同的target值&#xff0c;glTexParameteri函数的行为也会有所不同…...

linux时间的特殊用法

今天介绍linux下Date时间命令相关的特殊用法 date (当前的时间) 修改系统当前时间&#xff1a; date -s "2022-6-20 9:33:50" 昨天的时间是我们比较常用的&#xff1a; date -d "yesterday" %Y%m%d ( 昨天的时间) date -d "1 day ago" %Y%m%d …...

axios 封装,API接口统一管理

分享一个自己封装的 axios 网络请求 主要的功能及其优点&#xff1a; 将所有的接口放在一个文件夹中管理&#xff08;api.js&#xff09;。并且可以支持动态接口&#xff0c;就是 api.js 文件中定义的接口可以使用 :xx 占位&#xff0c;根据需要动态的改变。动态接口用法模仿…...

SpringBoot使用Redis实现缓存

目录 实现步骤 1. 在 pom.xml 配置文件中添加如下依赖 2. 在 application.properties 中添加如下配置 3. 新建 RedisConfig.class&#xff0c;继承 CachingConfigurerSupport&#xff0c;添加如下方法 4. 新建 RedisService.class 添加如下方法 注意&#xff1a;cacheKey…...

[失业前端恶补算法]JavaScript leetcode刷题top100(三)

专栏声明&#xff1a;只求用最简单的&#xff0c;容易理解的方法通过&#xff0c;不求优化&#xff0c;不喜勿喷 今天更新五个 easy 难度题目&#xff1a; 相交链表 题面 给你两个单链表的头节点 headA 和 headB &#xff0c;请你找出并返回两个单链表相交的起始节点。如果两个…...

Spark RDD的设计与运行原理

一、Spark RDD概念 一个RDD就是一个分布式对象集合&#xff0c;本质上是一个只读的分区记录集合&#xff0c;每个RDD可以分成多个分区&#xff0c;每个分区就是一个数据集片段&#xff0c;并且一个RDD的不同分区可以被保存到集群中不同的节点上&#xff0c;从而可以在集群中的…...

Golang的下载与安装

Windows系统 进入golang官方下载网站:所有版本 - Go 编程语言如图所示 下载后打开您下载的 MSI 文件,然后按照提示安装 Go。 验证是否已安装 Go。...

广州蓝景分享—8大Web前端开发的趋势

2023 年 1 月 11 日&#xff0c;2022 年度 StateOfJS 调查结果正式公布&#xff01;StateOfJS 是前端生态圈中比较有影响力的且规模较大的数据调查。本文就来解读一下 2022 年 StateOfJS 的调查结果&#xff01; JavaScript 发展很快&#xff0c;但似乎 JavaScript 开发人员的…...

Java学习-MySQL-创建数据库表

Java学习-MySQL-创建数据库表 SHOW DATABASESUSE school CREATE TABLE IF NOT EXISTS student( id INT(10) NOT NULL AUTO_INCREMENT COMMENT 学号, name VARCHAR(30) NOT NULL DEFAULT 匿名 COMMENT 姓名, pws VARCHAR(20) NOT NULL DEFAULT 123456 COMMENT 密码, sex VARCHA…...

Ethercat学习-GD32以太网学习

文章目录1、GD32F4以太网简介2、以太网模框图简介3、以太网主要模块介绍SMI接口RMII接口与MII接口DMA控制器4、以太网配置流程5、其他1、GD32F4以太网简介 GD32F4系列以太网模块包含10/100Mbps以太网MAC&#xff0c;数据的收发都通过DMA进行操作&#xff0c;支持MII&#xff0…...

项目规模估算如何精准 4大注意事项

项目报价&#xff0c;需要首先进行项目规模估算&#xff0c;如何估算更精准&#xff0c;6大注意事项。 1、项目范围规划 在项目估算前&#xff0c;需要对项目范围进行规划&#xff0c;这包括所有活动以及开发可交付产品所需的流程。范围规划是前提&#xff0c;它明确定义了项目…...

低代码:助力乡村振兴事业开启“智慧模式”

伴随着脱贫攻坚目标任务的全面完成&#xff0c;我国“三农”工作重心历史性地转向全面推进乡村振兴&#xff0c;这也标志着我国农业农村工作迈上了一个新台阶。 什么是乡村振兴&#xff1f; 乡村振兴是新时代“三农”工作的总抓手&#xff0c;坚持农业农村优先发展&#xff0c;…...

Flutter——Isolate主线机制

简述 在DartFlutter应用程序启动时&#xff0c;会启动一个主线程其实也就是Root Isolate,在Root Isolate内部运行一个EventLoop事件循环。所以所有的Dart代码都是运行在Isolate之中的&#xff0c;它就像是机器上的一个小空间&#xff0c;具有自己的私有内存块和一个运行事件循…...

提取游戏《Limbus Company》(边狱公司)内素材

授人以鱼&#xff0c;不如授人以渔。 目录 注意事项 寻找音频文件 .bytes转为.fsb 必备工具 步骤 解决乱码 必备工具 步骤 提取.fsb文件 必备工具 可备工具 步骤 注意事项 文章关于出现乱码的处理方法和与编码相关的部分有误&#xff0c;已于2023/3/10更正。 相关…...

学生信息表

目录 一、功能说明 二、核心思想 三、所用知识回顾 四、基本框架 五、js功能实现部分 一、功能说明 &#xff08;1&#xff09;输入对应的信息&#xff0c;点击录入可以为下面的表格添加一条记录&#xff0c;注意当所填信息不完整时不允许进行提交。 &#xff08;2&…...

FOTA在AUTOSAR中的应用

FOTA介绍 FOTA(Firmware Over-The-Air)移动终端的空中下载软件升级,指通过云端升级技术,为具有连网功能的设备:例如手机、平板电脑、便携式媒体播放器、移动互联网设备等提供固件升级服务,用户使用网络以按需、易扩展的方式获取智能终端系统升级包,并通过FOTA进行云端升…...

2023/3/10 Vue核心知识的学习- Vue - v-model双向绑定原理

https://www.jianshu.com/p/2682b5a26869 定义&#xff1a;vue中双向绑定就是指v-model指令&#xff0c;可以绑定一个响应式数据到视图&#xff0c;同时视图中变化能同步改变该值。 通过Object.defineProperty( )对属性设置一个set函数&#xff0c;当数据改变了就会来触发这个…...

Chapter03-Authentication vulnerabilities

文章目录 1. 身份验证简介1.1 What is authentication1.2 difference between authentication and authorization1.3 身份验证机制失效的原因1.4 身份验证机制失效的影响 2. 基于登录功能的漏洞2.1 密码爆破2.2 用户名枚举2.3 有缺陷的暴力破解防护2.3.1 如果用户登录尝试失败次…...

生成xcframework

打包 XCFramework 的方法 XCFramework 是苹果推出的一种多平台二进制分发格式&#xff0c;可以包含多个架构和平台的代码。打包 XCFramework 通常用于分发库或框架。 使用 Xcode 命令行工具打包 通过 xcodebuild 命令可以打包 XCFramework。确保项目已经配置好需要支持的平台…...

利用ngx_stream_return_module构建简易 TCP/UDP 响应网关

一、模块概述 ngx_stream_return_module 提供了一个极简的指令&#xff1a; return <value>;在收到客户端连接后&#xff0c;立即将 <value> 写回并关闭连接。<value> 支持内嵌文本和内置变量&#xff08;如 $time_iso8601、$remote_addr 等&#xff09;&a…...

UR 协作机器人「三剑客」:精密轻量担当(UR7e)、全能协作主力(UR12e)、重型任务专家(UR15)

UR协作机器人正以其卓越性能在现代制造业自动化中扮演重要角色。UR7e、UR12e和UR15通过创新技术和精准设计满足了不同行业的多样化需求。其中&#xff0c;UR15以其速度、精度及人工智能准备能力成为自动化领域的重要突破。UR7e和UR12e则在负载规格和市场定位上不断优化&#xf…...

《C++ 模板》

目录 函数模板 类模板 非类型模板参数 模板特化 函数模板特化 类模板的特化 模板&#xff0c;就像一个模具&#xff0c;里面可以将不同类型的材料做成一个形状&#xff0c;其分为函数模板和类模板。 函数模板 函数模板可以简化函数重载的代码。格式&#xff1a;templa…...

【SSH疑难排查】轻松解决新版OpenSSH连接旧服务器的“no matching...“系列算法协商失败问题

【SSH疑难排查】轻松解决新版OpenSSH连接旧服务器的"no matching..."系列算法协商失败问题 摘要&#xff1a; 近期&#xff0c;在使用较新版本的OpenSSH客户端连接老旧SSH服务器时&#xff0c;会遇到 "no matching key exchange method found"​, "n…...

【学习笔记】erase 删除顺序迭代器后迭代器失效的解决方案

目录 使用 erase 返回值继续迭代使用索引进行遍历 我们知道类似 vector 的顺序迭代器被删除后&#xff0c;迭代器会失效&#xff0c;因为顺序迭代器在内存中是连续存储的&#xff0c;元素删除后&#xff0c;后续元素会前移。 但一些场景中&#xff0c;我们又需要在执行删除操作…...

HubSpot推出与ChatGPT的深度集成引发兴奋与担忧

上周三&#xff0c;HubSpot宣布已构建与ChatGPT的深度集成&#xff0c;这一消息在HubSpot用户和营销技术观察者中引发了极大的兴奋&#xff0c;但同时也存在一些关于数据安全的担忧。 许多网络声音声称&#xff0c;这对SaaS应用程序和人工智能而言是一场范式转变。 但向任何技…...

MySQL 主从同步异常处理

阅读原文&#xff1a;https://www.xiaozaoshu.top/articles/mysql-m-s-update-pk MySQL 做双主&#xff0c;遇到的这个错误&#xff1a; Could not execute Update_rows event on table ... Error_code: 1032是 MySQL 主从复制时的经典错误之一&#xff0c;通常表示&#xff…...

ArcGIS Pro+ArcGIS给你的地图加上北回归线!

今天来看ArcGIS Pro和ArcGIS中如何给制作的中国地图或者其他大范围地图加上北回归线。 我们将在ArcGIS Pro和ArcGIS中一同介绍。 1 ArcGIS Pro中设置北回归线 1、在ArcGIS Pro中初步设置好经纬格网等&#xff0c;设置经线、纬线都以10间隔显示。 2、需要插入背会归线&#xf…...