【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】动态规划::前缀和(二)
标题:【leetcode】前缀和(二) 水墨不写bug 正文开始: (一) 和为K的子数组 给你一个整数数组 nums 和一个整数 k ,请你统计并返回 该数组中和为 k 的子数组的个数 。 子数组是数组中元素的连续…...

SpringBoot自动装配原理之@Import注解解析
文章目录 1. 概述2. 使用2.1 导入普通Bean2.2 导入配置类2.3 导入 ImportSelector 实现类2.4 导入 ImportBeanDefinitionRegistrar 实现类 3. 区别 1. 概述 当谈及现代Java开发领域中的框架选择时,SpringBoot无疑是无与伦比的热门之选。其简化了开发流程࿰…...

49 样式迁移【李沐动手学深度学习v2课程笔记】
1. 样式迁移(Style Transfer) 计算机视觉的应用之一,将样式图片中的样式(比如油画风格等)迁移到内容图片(比如实拍的图片)上,得到合成图片 可以理解成为一个滤镜,但相对于滤镜来讲…...

Linux的学习之路:4、权限
一、Linux权限的概念 权限我们都熟悉,最常见的就是在看电视时需要vip这个就是权限,然后在Linux就是有两个权限,就是管理员也就是超级用户和普通的用户 命令:su [用户名] 功能:切换用户。 例如,要从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概述作用一个简单的案例:使用JSP页面输出当前日期 JSP处理过程JSP 生命周期编译阶段初始化阶段执行阶段销毁阶段案例 JSP页面的元素JSP指令JSP中的page指令Include指令示例 taglib指令 JSP中的小脚本与表达式JSP中的声明JSP中的注释HTML的注释JSP注释 JSP行…...

外包干了25天,技术退步明显.......
先说一下自己的情况,大专生,18年通过校招进入杭州某软件公司,干了接近4年的功能测试,今年年初,感觉自己不能够在这样下去了,长时间呆在一个舒适的环境会让一个人堕落! 而我已经在一个企业干了四年的功能测…...
C++(14): STL条件变量std::condition_variable
1. 简述 在C的标准模板库(STL)中,std::condition_variable是一个非常重要的同步原语,用于在多线程编程中实现线程间的条件同步。它允许一个或多个线程等待某个条件成立,当条件成立时,等待的线程会被唤醒并继…...

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

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

Cohere推出全新升级版RAG大型AI模型:支持中文,搭载1040亿参数,现开源其权重!
4月5日,知名类ChatGPT平台Cohere在其官方网站上发布了一款全新的模型——Command R。 据官方消息,Command R拥有1040亿个参数,并且支持包括英语、中文、法语、德语在内的10种语言。这一模型的显著特点之一在于其对内置的RAG(检索增…...

搭建前后端的链接(java)
搭建前后端的链接(java) 一.前提 1.1 javaEE 搭建前后端的链接首先需要用到javaEE,也就是java企业版,也就是java后端(后端javaSE) 利用javaEE和前端交互,javaSE和数据库交互,javaSE和javaEE之间再进行交互就实现了前后端的交互…...
Java多路查找树(含面试大厂题和源码)
多路查找树(Multiway Search Tree),也称为B树或B树,是一种自平衡的树形数据结构,用于存储大量数据,通常用于数据库和文件系统中。它允许在查找、插入和删除操作中保持数据的有序性,同时优化了磁…...
day6 | 哈希表 part-2 | 454 四数相加II 、383. 赎金信、15. 三数之和、18. 四数之和
今日任务 454 四数相加II (题目: . - 力扣(LeetCode))383 赎金信 (题目: . - 力扣(LeetCode)) 454 四数相加II 题目:. - 力扣(LeetCode) 给你四个整数数组 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.消费端消息可靠性保证: 1.1 消息确认(Acknowledgements): 消费者在接收到消息后,默认情况下RabbitMQ会自动确认消息(autoAcktrue)。为保证消息可靠性,可以…...

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

生成随机图片验证码
随着互联网的不断发展,安全性问题日益突出。为了保障用户账号的安全性,很多网站都引入了验证码机制。验证码是一种区分用户是计算机还是人的公共全自动程序,可以有效防止恶意攻击和自动化脚本的滥用。本文将介绍如何使用Python生成随机图片验…...
[2025CVPR]DeepVideo-R1:基于难度感知回归GRPO的视频强化微调框架详解
突破视频大语言模型推理瓶颈,在多个视频基准上实现SOTA性能 一、核心问题与创新亮点 1.1 GRPO在视频任务中的两大挑战 安全措施依赖问题 GRPO使用min和clip函数限制策略更新幅度,导致: 梯度抑制:当新旧策略差异过大时梯度消失收敛困难:策略无法充分优化# 传统GRPO的梯…...
利用ngx_stream_return_module构建简易 TCP/UDP 响应网关
一、模块概述 ngx_stream_return_module 提供了一个极简的指令: return <value>;在收到客户端连接后,立即将 <value> 写回并关闭连接。<value> 支持内嵌文本和内置变量(如 $time_iso8601、$remote_addr 等)&a…...

python打卡day49
知识点回顾: 通道注意力模块复习空间注意力模块CBAM的定义 作业:尝试对今天的模型检查参数数目,并用tensorboard查看训练过程 import torch import torch.nn as nn# 定义通道注意力 class ChannelAttention(nn.Module):def __init__(self,…...

SCAU期末笔记 - 数据分析与数据挖掘题库解析
这门怎么题库答案不全啊日 来简单学一下子来 一、选择题(可多选) 将原始数据进行集成、变换、维度规约、数值规约是在以下哪个步骤的任务?(C) A. 频繁模式挖掘 B.分类和预测 C.数据预处理 D.数据流挖掘 A. 频繁模式挖掘:专注于发现数据中…...

学习STC51单片机31(芯片为STC89C52RCRC)OLED显示屏1
每日一言 生活的美好,总是藏在那些你咬牙坚持的日子里。 硬件:OLED 以后要用到OLED的时候找到这个文件 OLED的设备地址 SSD1306"SSD" 是品牌缩写,"1306" 是产品编号。 驱动 OLED 屏幕的 IIC 总线数据传输格式 示意图 …...
什么是EULA和DPA
文章目录 EULA(End User License Agreement)DPA(Data Protection Agreement)一、定义与背景二、核心内容三、法律效力与责任四、实际应用与意义 EULA(End User License Agreement) 定义: EULA即…...
爬虫基础学习day2
# 爬虫设计领域 工商:企查查、天眼查短视频:抖音、快手、西瓜 ---> 飞瓜电商:京东、淘宝、聚美优品、亚马逊 ---> 分析店铺经营决策标题、排名航空:抓取所有航空公司价格 ---> 去哪儿自媒体:采集自媒体数据进…...
大学生职业发展与就业创业指导教学评价
这里是引用 作为软工2203/2204班的学生,我们非常感谢您在《大学生职业发展与就业创业指导》课程中的悉心教导。这门课程对我们即将面临实习和就业的工科学生来说至关重要,而您认真负责的教学态度,让课程的每一部分都充满了实用价值。 尤其让我…...
Swagger和OpenApi的前世今生
Swagger与OpenAPI的关系演进是API标准化进程中的重要篇章,二者共同塑造了现代RESTful API的开发范式。 本期就扒一扒其技术演进的关键节点与核心逻辑: 🔄 一、起源与初创期:Swagger的诞生(2010-2014) 核心…...

C++ Visual Studio 2017厂商给的源码没有.sln文件 易兆微芯片下载工具加开机动画下载。
1.先用Visual Studio 2017打开Yichip YC31xx loader.vcxproj,再用Visual Studio 2022打开。再保侟就有.sln文件了。 易兆微芯片下载工具加开机动画下载 ExtraDownloadFile1Info.\logo.bin|0|0|10D2000|0 MFC应用兼容CMD 在BOOL CYichipYC31xxloaderDlg::OnIni…...