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

【leetcode】动态规划::前缀和(二)

标题:【leetcode】前缀和(二)

@水墨不写bug


 正文开始:

(一) 和为K的子数组

给你一个整数数组 nums 和一个整数 k ,请你统计并返回 该数组中和为 k 的子数组的个数 

子数组是数组中元素的连续非空序列。

示例 1:

输入:nums = [1,1,1], k = 2
输出:2

示例 2:

输入:nums = [1,2,3], k = 3
输出:2

提示:

  • 1 <= nums.length <= 2 * 10^4
  • -1000 <= nums[i] <= 1000
  • -10^7 <= k <= 10^7

 思路一:

        暴力求解,按照题目的描述来求解,对于每一个数,依次向后求和,如果和==k,此时不能停下来,ret++继续遍历到整个数组。很显然,此算法时间复杂度O(N^2),显然是会超时的算法。

思路二:

        我们可以换一种思路,现在我们聚焦于以下标 i 为结尾的和为k的数组,它们可能存在一个或者多个,甚至根本不存在;这时,我们已经固定了一个下标i,只需找到另一个下标即可;假设 i 之前存在一个下标 i0,[ i0 , i ](闭区间)的区间和为 k ,这时算出 以 i 为结尾的前缀和 sum[i],这就将问题:i之前是否存在i0,使得[ i0 , i ](闭区间)的区间和为 k —转化为了—> 下标 i 之前是否存在 i0 使得 i0 的前缀和为 sum[i] - k;

        这时如果你就按照以上思路来建立前缀和数组,然后使用数组时你就会后悔自己做过的事情了:在使用前缀和数组的时候,对于一个指针cur = i,需要向前遍历数组,在cur向后移动后,还要进行向前遍历,这个操作的时间复杂度为O(N^2),再加上建立前缀和数组的O(N),时间复杂度不减反增!

        这时我们就需要考虑,一些操作是否能够同时进行:将for的嵌套优化为一个for循环即可解决的问题。

        如何理解呢,其实一些互不影响的操作可以可以同时进行,这时我们就可以在同一个循环中同时进行多个操作,以此来减少for循环的个数,以此来降低时间复杂度。

        在本题中,由于前缀和前n项和在每次循环中只使用一次,所以可以创建一个变量,通过对变量进行迭代累加求和,来代替前缀和数组。

        sum是不断变化的,此时创建一个哈希表,目的是用来记录此时sum的值,在向后遍历时,sum会递增。

        创建变量ret累计和为k的字符串的个数;

        sum记录第i项的前缀和;

        创建hash表,用来向前找(sum-k)时 ret 累加 答案(sum-k)的个数。

参考代码: 

class Solution {
public:int subarraySum(vector<int>& nums, int k) {unordered_map<int,int> hash;int ret = 0,sum = 0;hash[0] = 1;for(auto x:nums){sum+=x;if(hash.count(sum-k)) ret += hash[sum-k];hash[sum]++;}return ret;}
};

(二)可被K整除的子数组

给定一个整数数组 nums 和一个整数 k ,返回其中元素之和可被 k 整除的(连续、非空) 子数组 的数目。

子数组 是数组的 连续 部分。

示例 1:

输入:nums = [4,5,0,-2,-3,1], k = 5
输出:7
解释:
有 7 个子数组满足其元素之和可被 k = 5 整除:
[4, 5, 0, -2, -3, 1], [5], [5, 0], [5, 0, -2, -3], [0], [0, -2, -3], [-2, -3]

示例 2:

输入: nums = [5], k = 9
输出: 0

提示:

  • 1 <= nums.length <= 3 * 104
  • -104 <= nums[i] <= 104
  • 2 <= k <= 104

class Solution {
public:int subarraysDivByK(vector<int>& nums, int k) {unordered_map<int,int> hash;hash[0%k] = 1;int sum = 0,ret = 0;for(const auto& e : nums){sum += e;//计算前缀和//判断是否有符合要求的前缀和int aim = (sum%k+k)%k;if(hash.count(aim)) ret += hash[aim];hash[aim]++;}return ret;}
};

(三)连续数组

给定一个二进制数组 nums , 找到含有相同数量的 0 和 1 的最长连续子数组,并返回该子数组的长度。

示例 1:

输入: nums = [0,1]
输出: 2
说明: [0, 1] 是具有相同数量 0 和 1 的最长连续子数组。

示例 2:

输入: nums = [0,1,0]
输出: 2
说明: [0, 1] (或 [1, 0]) 是具有相同数量0和1的最长连续子数组。

提示:

  • 1 <= nums.length <= 105
  • nums[i] 不是 0 就是 1

class Solution {
public:int findMaxLength(vector<int>& nums) {unordered_map<int,int> hash;//存前缀和与对应的下标hash[0] = -1;for( auto& e:nums) if(e == 0) e--;int ret = 0,sum = 0,n = nums.size();for(int i = 0;i < n;i++){sum += nums[i];if(hash.count(sum)) ret = max(ret,i-hash[sum]);else hash[sum] = i;}return ret;}
};

完~

未经作者同意禁止转载

相关文章:

【leetcode】动态规划::前缀和(二)

标题&#xff1a;【leetcode】前缀和&#xff08;二&#xff09; 水墨不写bug 正文开始&#xff1a; &#xff08;一&#xff09; 和为K的子数组 给你一个整数数组 nums 和一个整数 k &#xff0c;请你统计并返回 该数组中和为 k 的子数组的个数 。 子数组是数组中元素的连续…...

SpringBoot自动装配原理之@Import注解解析

文章目录 1. 概述2. 使用2.1 导入普通Bean2.2 导入配置类2.3 导入 ImportSelector 实现类2.4 导入 ImportBeanDefinitionRegistrar 实现类 3. 区别 1. 概述 当谈及现代Java开发领域中的框架选择时&#xff0c;SpringBoot无疑是无与伦比的热门之选。其简化了开发流程&#xff0…...

49 样式迁移【李沐动手学深度学习v2课程笔记】

1. 样式迁移&#xff08;Style Transfer) 计算机视觉的应用之一&#xff0c;将样式图片中的样式&#xff08;比如油画风格等&#xff09;迁移到内容图片&#xff08;比如实拍的图片&#xff09;上&#xff0c;得到合成图片 可以理解成为一个滤镜&#xff0c;但相对于滤镜来讲…...

Linux的学习之路:4、权限

一、Linux权限的概念 权限我们都熟悉&#xff0c;最常见的就是在看电视时需要vip这个就是权限&#xff0c;然后在Linux就是有两个权限&#xff0c;就是管理员也就是超级用户和普通的用户 命令&#xff1a;su [用户名] 功能&#xff1a;切换用户。 例如&#xff0c;要从root用户…...

自定义类型—结构体

目录 1 . 结构体类型的声明 1.1 结构的声明 1.2 结构体变量的创建与初始化 1.3 结构体的特殊声明 1.4 结构体的自引用 2. 结构体内存对齐 2.1 对齐规则 2.2 为什么存在内存对齐 2.3 修改默认对齐数 3. 结构体传参 4.结构体实现位段 4.1 位段的内存分配 4.3 位段的…...

【JavaWeb】Jsp基本教程

目录 JSP概述作用一个简单的案例&#xff1a;使用JSP页面输出当前日期 JSP处理过程JSP 生命周期编译阶段初始化阶段执行阶段销毁阶段案例 JSP页面的元素JSP指令JSP中的page指令Include指令示例 taglib指令 JSP中的小脚本与表达式JSP中的声明JSP中的注释HTML的注释JSP注释 JSP行…...

外包干了25天,技术退步明显.......

先说一下自己的情况&#xff0c;大专生&#xff0c;18年通过校招进入杭州某软件公司&#xff0c;干了接近4年的功能测试&#xff0c;今年年初&#xff0c;感觉自己不能够在这样下去了&#xff0c;长时间呆在一个舒适的环境会让一个人堕落! 而我已经在一个企业干了四年的功能测…...

C++(14): STL条件变量std::condition_variable

1. 简述 在C的标准模板库&#xff08;STL&#xff09;中&#xff0c;std::condition_variable是一个非常重要的同步原语&#xff0c;用于在多线程编程中实现线程间的条件同步。它允许一个或多个线程等待某个条件成立&#xff0c;当条件成立时&#xff0c;等待的线程会被唤醒并继…...

Harmony与Android项目结构对比

主要文件对应 Android文件HarmonyOS文件清单文件AndroidManifest.xmlmodule.json5Activity/Fragmententryability下的ts文件XML布局pages下的ets文件resresourcesModule下的build.gradleModule下的build-profile.json5gradlehvigor根目录下的build.gradle根目录下的build-profi…...

langchain 学习笔记-FunctionCalling三种方式

ChatGPT 基于海量的训练数据生成答案&#xff0c;所以它无法回答训练数据中没有的信息或搜索信息 。人们希望 ChatGPT 具有对话以外的各种功能&#xff0c;例如“我想管理我的待办事项列表”。 函数调用是对此类请求的响应。 通过使用函数调用&#xff0c;ChatGPT 现在可以在生…...

CNAS软件测试公司有什么好处?如何选择靠谱的软件测试公司?

CNAS认可是中国合格评定国家认可委员会的英文缩写&#xff0c;由国家认证认可监督管理委员会批准设立并授权的国家认可机构&#xff0c;统一负责对认证机构、实验室和检验机构等相关机构的认可工作。 在软件测试行业&#xff0c;CNAS认可具有重要意义。它标志着一个软件测试公…...

Cohere推出全新升级版RAG大型AI模型:支持中文,搭载1040亿参数,现开源其权重!

4月5日&#xff0c;知名类ChatGPT平台Cohere在其官方网站上发布了一款全新的模型——Command R。 据官方消息&#xff0c;Command R拥有1040亿个参数&#xff0c;并且支持包括英语、中文、法语、德语在内的10种语言。这一模型的显著特点之一在于其对内置的RAG&#xff08;检索增…...

搭建前后端的链接(java)

搭建前后端的链接(java) 一.前提 1.1 javaEE 搭建前后端的链接首先需要用到javaEE&#xff0c;也就是java企业版&#xff0c;也就是java后端(后端javaSE) 利用javaEE和前端交互&#xff0c;javaSE和数据库交互&#xff0c;javaSE和javaEE之间再进行交互就实现了前后端的交互…...

Java多路查找树(含面试大厂题和源码)

多路查找树&#xff08;Multiway Search Tree&#xff09;&#xff0c;也称为B树或B树&#xff0c;是一种自平衡的树形数据结构&#xff0c;用于存储大量数据&#xff0c;通常用于数据库和文件系统中。它允许在查找、插入和删除操作中保持数据的有序性&#xff0c;同时优化了磁…...

day6 | 哈希表 part-2 | 454 四数相加II 、383. 赎金信、15. 三数之和、18. 四数之和

今日任务 454 四数相加II (题目: . - 力扣&#xff08;LeetCode&#xff09;)383 赎金信 &#xff08;题目: . - 力扣&#xff08;LeetCode&#xff09;&#xff09; 454 四数相加II 题目&#xff1a;. - 力扣&#xff08;LeetCode&#xff09; 给你四个整数数组 nums1、num…...

Redis常见数据类型(2)

目录 String字符串 常见命令 SET GET MGET MSET SETNX 计数命令 INCR INCRBY DECR DECRBY INCRFLOAT 其它命令 APPEND GETRANGE SETRANGE STRLEN String字符串 字符串是Redis最基础的数据类型, 关于字符串需要特别注意: (1)首先Redis中所有的键的类型都是字符…...

SparkBug解决:Type mismatch; found : org.apache.spark.sql.Column required: Double

def assginFlag(aizmuth:Double):Option[Int] {val interval 0.5val index (aizmuth / interval ).toIntif (index > 0 && index < 720 ) Some(index 1) else None} assginFlag方法中的条件判断条件 (index > 0 && index < 720) 返回的是一个布…...

MQ之————如何保证消息的可靠性

MQ之保证消息的可靠性 1.消费端消息可靠性保证&#xff1a; 1.1 消息确认&#xff08;Acknowledgements&#xff09;&#xff1a; 消费者在接收到消息后&#xff0c;默认情况下RabbitMQ会自动确认消息&#xff08;autoAcktrue&#xff09;。为保证消息可靠性&#xff0c;可以…...

TrollInstallerX官方一键安装巨魔商店

TrollInstallerX是巨魔官方开发的一款一键巨魔商店安装器&#xff0c;完美支持iOS 14.0 – 16.6.1的设备&#xff0c;操作非常简单&#xff0c;TrollInstallerX依然有个小小的限制&#xff0c;部分机型&#xff0c;还是要采用间接安装方法。 一&#xff0c;直接安装方法 通过…...

生成随机图片验证码

随着互联网的不断发展&#xff0c;安全性问题日益突出。为了保障用户账号的安全性&#xff0c;很多网站都引入了验证码机制。验证码是一种区分用户是计算机还是人的公共全自动程序&#xff0c;可以有效防止恶意攻击和自动化脚本的滥用。本文将介绍如何使用Python生成随机图片验…...

idea大量爆红问题解决

问题描述 在学习和工作中&#xff0c;idea是程序员不可缺少的一个工具&#xff0c;但是突然在有些时候就会出现大量爆红的问题&#xff0c;发现无法跳转&#xff0c;无论是关机重启或者是替换root都无法解决 就是如上所展示的问题&#xff0c;但是程序依然可以启动。 问题解决…...

地震勘探——干扰波识别、井中地震时距曲线特点

目录 干扰波识别反射波地震勘探的干扰波 井中地震时距曲线特点 干扰波识别 有效波&#xff1a;可以用来解决所提出的地质任务的波&#xff1b;干扰波&#xff1a;所有妨碍辨认、追踪有效波的其他波。 地震勘探中&#xff0c;有效波和干扰波是相对的。例如&#xff0c;在反射波…...

Linux相关概念和易错知识点(42)(TCP的连接管理、可靠性、面临复杂网络的处理)

目录 1.TCP的连接管理机制&#xff08;1&#xff09;三次握手①握手过程②对握手过程的理解 &#xff08;2&#xff09;四次挥手&#xff08;3&#xff09;握手和挥手的触发&#xff08;4&#xff09;状态切换①挥手过程中状态的切换②握手过程中状态的切换 2.TCP的可靠性&…...

【JVM】- 内存结构

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

【第二十一章 SDIO接口(SDIO)】

第二十一章 SDIO接口 目录 第二十一章 SDIO接口(SDIO) 1 SDIO 主要功能 2 SDIO 总线拓扑 3 SDIO 功能描述 3.1 SDIO 适配器 3.2 SDIOAHB 接口 4 卡功能描述 4.1 卡识别模式 4.2 卡复位 4.3 操作电压范围确认 4.4 卡识别过程 4.5 写数据块 4.6 读数据块 4.7 数据流…...

在四层代理中还原真实客户端ngx_stream_realip_module

一、模块原理与价值 PROXY Protocol 回溯 第三方负载均衡&#xff08;如 HAProxy、AWS NLB、阿里 SLB&#xff09;发起上游连接时&#xff0c;将真实客户端 IP/Port 写入 PROXY Protocol v1/v2 头。Stream 层接收到头部后&#xff0c;ngx_stream_realip_module 从中提取原始信息…...

页面渲染流程与性能优化

页面渲染流程与性能优化详解&#xff08;完整版&#xff09; 一、现代浏览器渲染流程&#xff08;详细说明&#xff09; 1. 构建DOM树 浏览器接收到HTML文档后&#xff0c;会逐步解析并构建DOM&#xff08;Document Object Model&#xff09;树。具体过程如下&#xff1a; (…...

视频字幕质量评估的大规模细粒度基准

大家读完觉得有帮助记得关注和点赞&#xff01;&#xff01;&#xff01; 摘要 视频字幕在文本到视频生成任务中起着至关重要的作用&#xff0c;因为它们的质量直接影响所生成视频的语义连贯性和视觉保真度。尽管大型视觉-语言模型&#xff08;VLMs&#xff09;在字幕生成方面…...

土地利用/土地覆盖遥感解译与基于CLUE模型未来变化情景预测;从基础到高级,涵盖ArcGIS数据处理、ENVI遥感解译与CLUE模型情景模拟等

&#x1f50d; 土地利用/土地覆盖数据是生态、环境和气象等诸多领域模型的关键输入参数。通过遥感影像解译技术&#xff0c;可以精准获取历史或当前任何一个区域的土地利用/土地覆盖情况。这些数据不仅能够用于评估区域生态环境的变化趋势&#xff0c;还能有效评价重大生态工程…...

聊一聊接口测试的意义有哪些?

目录 一、隔离性 & 早期测试 二、保障系统集成质量 三、验证业务逻辑的核心层 四、提升测试效率与覆盖度 五、系统稳定性的守护者 六、驱动团队协作与契约管理 七、性能与扩展性的前置评估 八、持续交付的核心支撑 接口测试的意义可以从四个维度展开&#xff0c;首…...