【算法挨揍日记】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. 基础推荐 假设您作为一个深度学习入门学者的需求,以下是一份推荐的电脑硬件配…...
[特殊字符] 智能合约中的数据是如何在区块链中保持一致的?
🧠 智能合约中的数据是如何在区块链中保持一致的? 为什么所有区块链节点都能得出相同结果?合约调用这么复杂,状态真能保持一致吗?本篇带你从底层视角理解“状态一致性”的真相。 一、智能合约的数据存储在哪里…...
k8s从入门到放弃之Ingress七层负载
k8s从入门到放弃之Ingress七层负载 在Kubernetes(简称K8s)中,Ingress是一个API对象,它允许你定义如何从集群外部访问集群内部的服务。Ingress可以提供负载均衡、SSL终结和基于名称的虚拟主机等功能。通过Ingress,你可…...
MySQL 隔离级别:脏读、幻读及不可重复读的原理与示例
一、MySQL 隔离级别 MySQL 提供了四种隔离级别,用于控制事务之间的并发访问以及数据的可见性,不同隔离级别对脏读、幻读、不可重复读这几种并发数据问题有着不同的处理方式,具体如下: 隔离级别脏读不可重复读幻读性能特点及锁机制读未提交(READ UNCOMMITTED)允许出现允许…...
从零实现富文本编辑器#5-编辑器选区模型的状态结构表达
先前我们总结了浏览器选区模型的交互策略,并且实现了基本的选区操作,还调研了自绘选区的实现。那么相对的,我们还需要设计编辑器的选区表达,也可以称为模型选区。编辑器中应用变更时的操作范围,就是以模型选区为基准来…...
连锁超市冷库节能解决方案:如何实现超市降本增效
在连锁超市冷库运营中,高能耗、设备损耗快、人工管理低效等问题长期困扰企业。御控冷库节能解决方案通过智能控制化霜、按需化霜、实时监控、故障诊断、自动预警、远程控制开关六大核心技术,实现年省电费15%-60%,且不改动原有装备、安装快捷、…...
376. Wiggle Subsequence
376. Wiggle Subsequence 代码 class Solution { public:int wiggleMaxLength(vector<int>& nums) {int n nums.size();int res 1;int prediff 0;int curdiff 0;for(int i 0;i < n-1;i){curdiff nums[i1] - nums[i];if( (prediff > 0 && curdif…...
linux arm系统烧录
1、打开瑞芯微程序 2、按住linux arm 的 recover按键 插入电源 3、当瑞芯微检测到有设备 4、松开recover按键 5、选择升级固件 6、点击固件选择本地刷机的linux arm 镜像 7、点击升级 (忘了有没有这步了 估计有) 刷机程序 和 镜像 就不提供了。要刷的时…...
select、poll、epoll 与 Reactor 模式
在高并发网络编程领域,高效处理大量连接和 I/O 事件是系统性能的关键。select、poll、epoll 作为 I/O 多路复用技术的代表,以及基于它们实现的 Reactor 模式,为开发者提供了强大的工具。本文将深入探讨这些技术的底层原理、优缺点。 一、I…...
RNN避坑指南:从数学推导到LSTM/GRU工业级部署实战流程
本文较长,建议点赞收藏,以免遗失。更多AI大模型应用开发学习视频及资料,尽在聚客AI学院。 本文全面剖析RNN核心原理,深入讲解梯度消失/爆炸问题,并通过LSTM/GRU结构实现解决方案,提供时间序列预测和文本生成…...
Unity | AmplifyShaderEditor插件基础(第七集:平面波动shader)
目录 一、👋🏻前言 二、😈sinx波动的基本原理 三、😈波动起来 1.sinx节点介绍 2.vertexPosition 3.集成Vector3 a.节点Append b.连起来 4.波动起来 a.波动的原理 b.时间节点 c.sinx的处理 四、🌊波动优化…...




