【算法挨揍日记】day15——560. 和为 K 的子数组、974. 和可被 K 整除的子数组

560. 和为 K 的子数组
560. 和为 K 的子数组
题目描述:
给你一个整数数组 nums 和一个整数 k ,请你统计并返回 该数组中和为 k 的连续子数组的个数 。
子数组是数组中元素的连续非空序列。
解题思路:
我们可以很容易想到暴力解法,但是时间复杂度为N^2,我们可以是用前缀和对其优化
我们可以利用前缀和数组sum来记录,sum【i】代表到i位置的子数组之和
假设这是0-i的数组后面的我们先不看,我们可以将其分成两部分,一部分之和为k,另外一部分为sum【i】-k,本题是求和为k的数组的个数
那问题就可以变为在sum【i】-k中有多少个子数组等于sum【i】-k
这段区间正负都有,子区间可能不只有一个噢!!!
我们可以利用hash来完成本题,一个参数为前缀和,一个参数为次数 ,都是int类型
我们可以利用一个int变量来代替sum数组,因为sum不用每个都记录下来,只要记录上一个位置
解题代码:
class Solution {
public:int subarraySum(vector<int>& nums, int k) {unordered_map<int,int>hash;hash[0]=1;int ret=0;int sum=0;for(auto x:nums){sum+=x;if(hash.count(sum-k))ret+=hash[sum-k];hash[sum]++;}return ret;}
};
974. 和可被 K 整除的子数组
974. 和可被 K 整除的子数组
题目描述:
给定一个整数数组 nums 和一个整数 k ,返回其中元素之和可被 k 整除的(连续、非空) 子数组 的数目。
子数组 是数组的 连续 部分。
解题思路:
解决本题我们先来补充两个知识点
- 同余定理:(a-b)/p=k....0可以转换为a%p=b%p,具体证明可见同余定理_百度百科 (baidu.com)
- C++中,负数(a)%正数(p),在C++负数求余正数正确应该为正数,但是计算结果为负数,我们对其修正时期变成a%p+p,但是为了考虑到正负统一的问题,我们再次进行修正让其变为(a%p+p)%p
接下来我们来看一下本题,本题如果你做了上一题,你会发现基本上是类似的
只不过判断条件不太一样罢了
题目要求的可以被k整除的数组为图中sum-x部分,那就变成(sum-x)%k==0也就变成了sum%k==x%k,也就转为为在【0,i-1】这个区间内有多少个前缀和的余数等于sum%k
解题代码:
class Solution {
public:int subarraysDivByK(vector<int>& nums, int k) {unordered_map<int,int>hash;hash[0%k]=1;int ret=0;int sum=0;for(auto x:nums){sum+=x;int r=(sum%k+k)%k;if(hash.count(r))ret+=hash[r];hash[r]++;}return ret;}
};

相关文章:
【算法挨揍日记】day15——560. 和为 K 的子数组、974. 和可被 K 整除的子数组
560. 和为 K 的子数组 560. 和为 K 的子数组 题目描述: 给你一个整数数组 nums 和一个整数 k ,请你统计并返回 该数组中和为 k 的连续子数组的个数 。 子数组是数组中元素的连续非空序列。 解题思路: 我们可以很容易想到暴力解法…...
数字时代的探索与革新:Socks5代理的引领作用
在当今快速发展的数字时代,技术创新推动着社会的变革与进步。Socks5代理作为一项重要的网络技术,正引领着跨界电商、爬虫数据分析、企业全球化和游戏体验优化等领域的发展。本文将深入探讨Socks5代理技术在这些领域中的引领作用,以及它如何塑…...
算法-堆/归并排序-排序链表
算法-堆/归并排序-排序链表 1 题目概述 1.1 题目出处 https://leetcode.cn/problems/sort-list/description/?envTypestudy-plan-v2&envIdtop-interview-150 1.2 题目描述 2 优先级队列构建大顶堆 2.1 思路 优先级队列构建小顶堆链表所有元素放入小顶堆依次取出堆顶…...
word 如何编写4x4矩阵
百度上给的教程,打印出来没有对齐 https://jingyan.baidu.com/article/6b182309995f8dba58e159fc.html 百度上的方式试了一下,不会对齐。导致公式看起来很奇怪。 下面方式会自动对齐 摸索了一下发现可以用下面这种方式编写 4x4 矩阵。先创建一个 3x3…...
INTELlij IDEA编辑VUE项目
菜单中选择setting–>Plugins 或者快捷键 ctrlalts 搜索vue,但有些情况会搜索不出来,先说搜索到的情况 如下图所示: 如果没有vue.js则说明过去已经安装了。 搜索到了后点击Install安装即可, 但即使搜索成功了,也不…...
linux进程间通讯--信号量
1.认识信号量 方便理解:信号量就是一个计数器。当它大于0能用,小于等于0,用不了,这个值自己给。 2.特点: 信号量用于进程间同步,若要在进程间传递数据需要结合共享内存。信号量基于操作系统的 PV 操作&am…...
VS Code连接远程Linux服务器开发c++项目
1.在远程 Linux 上安装包 yum groupinstall "development tools" -y yum install cmake -y2.在 VSCode 上安装插件 C/CC/C Extension PackCMakeCMake ToolsCMake Language Support 3.连接远程Linux服务器...
stable diffusion的模型选择,采样器选择,关键词
一、Stable Diffusion的模型选择: 模型下载地址:https://civitai.com/,需要科学上网。 Deliberate:全能模型,prompt越详细生成的图片质量越好Realistic Vision:现实模型,生成仿真式图片&#…...
BI零售数据分析:以自身视角展开分析
随着零售业务不断扩展,市场竞争不断加剧,各层级的销售管理人员都急需一张能快速查看销售数据分析报表,能从中知道自己管辖内的业务最近或过去的情况,并依次为依据科学优化销售管理措施。这就要求零售数据分析报表信息足够多、数据…...
Maven 使用教程(三)
一、如何使用外部依赖项? 您可能已经注意到POM中的一个dependencies元素,我们一直在使用它作为示例。事实上,您一直在使用外部依赖项,但在这里我们将更详细地讨论它是如何工作的。有关更全面的介绍,请参阅我们的依赖机…...
行秋找工作的记录
2023-10-17 15:35-16:00 中移(苏州)研发中心面试 问了项目,还有一些我没准备到的Java八股文:Java类的加载过程,发射机制,redis存储结构,二叉平衡树等。但我也都没回答上来。应该无了。 2023-1…...
vue项目打包,使用externals抽离公共的第三方库
封装了一个插件,用来vue打包抽离公共的第三方库,使用unplugin进行插件开发,vite对应的功能使用了vite-plugin-externals进行二次开发 github地址 npm地址 hfex-auto-externals-plugin 自动注入插件,使用 unplugin 和 html-webpack-plugin进…...
九阳真经之各大厂校招
大学计算机系的同学要怎么努力才能校招进大厂? 秋招的大公司非常多,也是非常好的,赶上了秋招,你基本工作就敲定了,在整个应届毕业生的人群中你就占据很大的优势了。 如何准备应届校招? 一、做好规划,把…...
Go语言入门心法(五): 函数
Go语言入门心法(一): 基础语法 Go语言入门心法(二): 结构体 Go语言入门心法(三): 接口 Go语言入门心法(四): 异常体系 Go语言入门心法(五): 函数 一: go语言函数认知 函数相关认知升维:函数的功能就是把相对独立的某个相同或者时类型的功能抽象处理,使之成为一个…...
gitignore文件的语法规则
行注释:以"#"符号开头的行表示注释,Git会忽略这些行。空行:空行会被忽略。文件和目录规则: 可以使用通配符来匹配文件和目录。常用的通配符有: “*”:匹配0个或多个字符。“?”:匹配…...
vscode提示扩展主机在过去5分钟内意外终止了3次,解决方法
参考链接: https://code.visualstudio.com/blogs/2021/02/16/extension-bisect https://code.visualstudio.com/docs/setup/uninstall#_clean-uninstall 使用vscode打开jupyter notebook记事本时,窗口右下角提示扩展主机在过去5分钟内意外终止了3次 而…...
【算法挨揍日记】day16——525. 连续数组、1314. 矩阵区域和
525. 连续数组 525. 连续数组 题目描述: 给定一个二进制数组 nums , 找到含有相同数量的 0 和 1 的最长连续子数组,并返回该子数组的长度。 解题思路: 本题的元素只有0和1,根据题目意思,我们可以把题目看成找一段最…...
k8s-13 存储之secret
Secret 对象类型用来保存敏感信息,例如密码、OAuth 令牌和 ssh key。 敏感信息放在 secret 中比放在 Pod 的定义或者容器镜像中来说更加安全和灵活 。 Pod 可以用两种方式使用 secret:作为 volume 中的文件被挂载到 pod 中的一个或者多个容器里 当 kubelet 为 pod 拉…...
什么是高阶成分(HOC)
高阶组件(Higher-Order Component,HOC)是一种在React中用于组件复用和逻辑抽象的设计模式。它本质上是一个函数,接受一个组件作为参数,并返回一个新的组件。 1. HOC的作用: HOC允许我们在不修改原始组件的…...
深度学习硬件配置推荐
目录 1. 基础推荐2. GPU显存与内存是一个1:4的配比?3. deep learning 入门和kaggle比赛4. 有些 Kaggle 比赛数据集很大,可能需要更多的 GPU 显存,请推荐显存4. GDDR6和HBM25. HDD 或 SATA SSD1. 基础推荐 假设您作为一个深度学习入门学者的需求,以下是一份推荐的电脑硬件配…...
OpenLayers 可视化之热力图
注:当前使用的是 ol 5.3.0 版本,天地图使用的key请到天地图官网申请,并替换为自己的key 热力图(Heatmap)又叫热点图,是一种通过特殊高亮显示事物密度分布、变化趋势的数据可视化技术。采用颜色的深浅来显示…...
论文解读:交大港大上海AI Lab开源论文 | 宇树机器人多姿态起立控制强化学习框架(二)
HoST框架核心实现方法详解 - 论文深度解读(第二部分) 《Learning Humanoid Standing-up Control across Diverse Postures》 系列文章: 论文深度解读 + 算法与代码分析(二) 作者机构: 上海AI Lab, 上海交通大学, 香港大学, 浙江大学, 香港中文大学 论文主题: 人形机器人…...
rknn优化教程(二)
文章目录 1. 前述2. 三方库的封装2.1 xrepo中的库2.2 xrepo之外的库2.2.1 opencv2.2.2 rknnrt2.2.3 spdlog 3. rknn_engine库 1. 前述 OK,开始写第二篇的内容了。这篇博客主要能写一下: 如何给一些三方库按照xmake方式进行封装,供调用如何按…...
【大模型RAG】Docker 一键部署 Milvus 完整攻略
本文概要 Milvus 2.5 Stand-alone 版可通过 Docker 在几分钟内完成安装;只需暴露 19530(gRPC)与 9091(HTTP/WebUI)两个端口,即可让本地电脑通过 PyMilvus 或浏览器访问远程 Linux 服务器上的 Milvus。下面…...
连锁超市冷库节能解决方案:如何实现超市降本增效
在连锁超市冷库运营中,高能耗、设备损耗快、人工管理低效等问题长期困扰企业。御控冷库节能解决方案通过智能控制化霜、按需化霜、实时监控、故障诊断、自动预警、远程控制开关六大核心技术,实现年省电费15%-60%,且不改动原有装备、安装快捷、…...
工程地质软件市场:发展现状、趋势与策略建议
一、引言 在工程建设领域,准确把握地质条件是确保项目顺利推进和安全运营的关键。工程地质软件作为处理、分析、模拟和展示工程地质数据的重要工具,正发挥着日益重要的作用。它凭借强大的数据处理能力、三维建模功能、空间分析工具和可视化展示手段&…...
ABAP设计模式之---“简单设计原则(Simple Design)”
“Simple Design”(简单设计)是软件开发中的一个重要理念,倡导以最简单的方式实现软件功能,以确保代码清晰易懂、易维护,并在项目需求变化时能够快速适应。 其核心目标是避免复杂和过度设计,遵循“让事情保…...
C++使用 new 来创建动态数组
问题: 不能使用变量定义数组大小 原因: 这是因为数组在内存中是连续存储的,编译器需要在编译阶段就确定数组的大小,以便正确地分配内存空间。如果允许使用变量来定义数组的大小,那么编译器就无法在编译时确定数组的大…...
NPOI Excel用OLE对象的形式插入文件附件以及插入图片
static void Main(string[] args) {XlsWithObjData();Console.WriteLine("输出完成"); }static void XlsWithObjData() {// 创建工作簿和单元格,只有HSSFWorkbook,XSSFWorkbook不可以HSSFWorkbook workbook new HSSFWorkbook();HSSFSheet sheet (HSSFSheet)workboo…...
【 java 虚拟机知识 第一篇 】
目录 1.内存模型 1.1.JVM内存模型的介绍 1.2.堆和栈的区别 1.3.栈的存储细节 1.4.堆的部分 1.5.程序计数器的作用 1.6.方法区的内容 1.7.字符串池 1.8.引用类型 1.9.内存泄漏与内存溢出 1.10.会出现内存溢出的结构 1.内存模型 1.1.JVM内存模型的介绍 内存模型主要分…...




