当前位置: 首页 > 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生成随机图片验…...

[2025CVPR]DeepVideo-R1:基于难度感知回归GRPO的视频强化微调框架详解

突破视频大语言模型推理瓶颈,在多个视频基准上实现SOTA性能 一、核心问题与创新亮点 1.1 GRPO在视频任务中的两大挑战 ​安全措施依赖问题​ GRPO使用min和clip函数限制策略更新幅度,导致: 梯度抑制:当新旧策略差异过大时梯度消失收敛困难:策略无法充分优化# 传统GRPO的梯…...

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

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

python打卡day49

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

SCAU期末笔记 - 数据分析与数据挖掘题库解析

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

学习STC51单片机31(芯片为STC89C52RCRC)OLED显示屏1

每日一言 生活的美好&#xff0c;总是藏在那些你咬牙坚持的日子里。 硬件&#xff1a;OLED 以后要用到OLED的时候找到这个文件 OLED的设备地址 SSD1306"SSD" 是品牌缩写&#xff0c;"1306" 是产品编号。 驱动 OLED 屏幕的 IIC 总线数据传输格式 示意图 …...

什么是EULA和DPA

文章目录 EULA&#xff08;End User License Agreement&#xff09;DPA&#xff08;Data Protection Agreement&#xff09;一、定义与背景二、核心内容三、法律效力与责任四、实际应用与意义 EULA&#xff08;End User License Agreement&#xff09; 定义&#xff1a; EULA即…...

爬虫基础学习day2

# 爬虫设计领域 工商&#xff1a;企查查、天眼查短视频&#xff1a;抖音、快手、西瓜 ---> 飞瓜电商&#xff1a;京东、淘宝、聚美优品、亚马逊 ---> 分析店铺经营决策标题、排名航空&#xff1a;抓取所有航空公司价格 ---> 去哪儿自媒体&#xff1a;采集自媒体数据进…...

大学生职业发展与就业创业指导教学评价

这里是引用 作为软工2203/2204班的学生&#xff0c;我们非常感谢您在《大学生职业发展与就业创业指导》课程中的悉心教导。这门课程对我们即将面临实习和就业的工科学生来说至关重要&#xff0c;而您认真负责的教学态度&#xff0c;让课程的每一部分都充满了实用价值。 尤其让我…...

Swagger和OpenApi的前世今生

Swagger与OpenAPI的关系演进是API标准化进程中的重要篇章&#xff0c;二者共同塑造了现代RESTful API的开发范式。 本期就扒一扒其技术演进的关键节点与核心逻辑&#xff1a; &#x1f504; 一、起源与初创期&#xff1a;Swagger的诞生&#xff08;2010-2014&#xff09; 核心…...

C++ Visual Studio 2017厂商给的源码没有.sln文件 易兆微芯片下载工具加开机动画下载。

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