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

【算法挨揍日记】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 的子数组 题目描述&#xff1a; 给你一个整数数组 nums 和一个整数 k &#xff0c;请你统计并返回 该数组中和为 k 的连续子数组的个数 。 子数组是数组中元素的连续非空序列。 解题思路&#xff1a; 我们可以很容易想到暴力解法&#xf…...

数字时代的探索与革新:Socks5代理的引领作用

在当今快速发展的数字时代&#xff0c;技术创新推动着社会的变革与进步。Socks5代理作为一项重要的网络技术&#xff0c;正引领着跨界电商、爬虫数据分析、企业全球化和游戏体验优化等领域的发展。本文将深入探讨Socks5代理技术在这些领域中的引领作用&#xff0c;以及它如何塑…...

算法-堆/归并排序-排序链表

算法-堆/归并排序-排序链表 1 题目概述 1.1 题目出处 https://leetcode.cn/problems/sort-list/description/?envTypestudy-plan-v2&envIdtop-interview-150 1.2 题目描述 2 优先级队列构建大顶堆 2.1 思路 优先级队列构建小顶堆链表所有元素放入小顶堆依次取出堆顶…...

word 如何编写4x4矩阵

百度上给的教程&#xff0c;打印出来没有对齐 https://jingyan.baidu.com/article/6b182309995f8dba58e159fc.html 百度上的方式试了一下&#xff0c;不会对齐。导致公式看起来很奇怪。 下面方式会自动对齐 摸索了一下发现可以用下面这种方式编写 4x4 矩阵。先创建一个 3x3…...

INTELlij IDEA编辑VUE项目

菜单中选择setting–>Plugins 或者快捷键 ctrlalts 搜索vue&#xff0c;但有些情况会搜索不出来&#xff0c;先说搜索到的情况 如下图所示&#xff1a; 如果没有vue.js则说明过去已经安装了。 搜索到了后点击Install安装即可&#xff0c; 但即使搜索成功了&#xff0c;也不…...

linux进程间通讯--信号量

1.认识信号量 方便理解&#xff1a;信号量就是一个计数器。当它大于0能用&#xff0c;小于等于0&#xff0c;用不了&#xff0c;这个值自己给。 2.特点&#xff1a; 信号量用于进程间同步&#xff0c;若要在进程间传递数据需要结合共享内存。信号量基于操作系统的 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的模型选择&#xff1a; 模型下载地址&#xff1a;https://civitai.com/&#xff0c;需要科学上网。 Deliberate&#xff1a;全能模型&#xff0c;prompt越详细生成的图片质量越好Realistic Vision&#xff1a;现实模型&#xff0c;生成仿真式图片&#…...

BI零售数据分析:以自身视角展开分析

随着零售业务不断扩展&#xff0c;市场竞争不断加剧&#xff0c;各层级的销售管理人员都急需一张能快速查看销售数据分析报表&#xff0c;能从中知道自己管辖内的业务最近或过去的情况&#xff0c;并依次为依据科学优化销售管理措施。这就要求零售数据分析报表信息足够多、数据…...

Maven 使用教程(三)

一、如何使用外部依赖项&#xff1f; 您可能已经注意到POM中的一个dependencies元素&#xff0c;我们一直在使用它作为示例。事实上&#xff0c;您一直在使用外部依赖项&#xff0c;但在这里我们将更详细地讨论它是如何工作的。有关更全面的介绍&#xff0c;请参阅我们的依赖机…...

行秋找工作的记录

2023-10-17 15:35-16:00 中移&#xff08;苏州&#xff09;研发中心面试 问了项目&#xff0c;还有一些我没准备到的Java八股文&#xff1a;Java类的加载过程&#xff0c;发射机制&#xff0c;redis存储结构&#xff0c;二叉平衡树等。但我也都没回答上来。应该无了。 2023-1…...

vue项目打包,使用externals抽离公共的第三方库

封装了一个插件&#xff0c;用来vue打包抽离公共的第三方库&#xff0c;使用unplugin进行插件开发&#xff0c;vite对应的功能使用了vite-plugin-externals进行二次开发 github地址 npm地址 hfex-auto-externals-plugin 自动注入插件,使用 unplugin 和 html-webpack-plugin进…...

九阳真经之各大厂校招

大学计算机系的同学要怎么努力才能校招进大厂? 秋招的大公司非常多&#xff0c;也是非常好的&#xff0c;赶上了秋招&#xff0c;你基本工作就敲定了&#xff0c;在整个应届毕业生的人群中你就占据很大的优势了。 如何准备应届校招&#xff1f; 一、做好规划&#xff0c;把…...

Go语言入门心法(五): 函数

Go语言入门心法(一): 基础语法 Go语言入门心法(二): 结构体 Go语言入门心法(三): 接口 Go语言入门心法(四): 异常体系 Go语言入门心法(五): 函数 一: go语言函数认知 函数相关认知升维&#xff1a;函数的功能就是把相对独立的某个相同或者时类型的功能抽象处理,使之成为一个…...

gitignore文件的语法规则

行注释&#xff1a;以"#"符号开头的行表示注释&#xff0c;Git会忽略这些行。空行&#xff1a;空行会被忽略。文件和目录规则&#xff1a; 可以使用通配符来匹配文件和目录。常用的通配符有&#xff1a; “*”&#xff1a;匹配0个或多个字符。“?”&#xff1a;匹配…...

vscode提示扩展主机在过去5分钟内意外终止了3次,解决方法

参考链接&#xff1a; https://code.visualstudio.com/blogs/2021/02/16/extension-bisect https://code.visualstudio.com/docs/setup/uninstall#_clean-uninstall 使用vscode打开jupyter notebook记事本时&#xff0c;窗口右下角提示扩展主机在过去5分钟内意外终止了3次 而…...

【算法挨揍日记】day16——525. 连续数组、1314. 矩阵区域和

525. 连续数组 525. 连续数组 题目描述&#xff1a; 给定一个二进制数组 nums , 找到含有相同数量的 0 和 1 的最长连续子数组&#xff0c;并返回该子数组的长度。 解题思路&#xff1a; 本题的元素只有0和1&#xff0c;根据题目意思&#xff0c;我们可以把题目看成找一段最…...

k8s-13 存储之secret

Secret 对象类型用来保存敏感信息&#xff0c;例如密码、OAuth 令牌和 ssh key。 敏感信息放在 secret 中比放在 Pod 的定义或者容器镜像中来说更加安全和灵活 。 Pod 可以用两种方式使用 secret:作为 volume 中的文件被挂载到 pod 中的一个或者多个容器里 当 kubelet 为 pod 拉…...

什么是高阶成分(HOC)

高阶组件&#xff08;Higher-Order Component&#xff0c;HOC&#xff09;是一种在React中用于组件复用和逻辑抽象的设计模式。它本质上是一个函数&#xff0c;接受一个组件作为参数&#xff0c;并返回一个新的组件。 1. HOC的作用&#xff1a; HOC允许我们在不修改原始组件的…...

深度学习硬件配置推荐

目录 1. 基础推荐2. GPU显存与内存是一个1:4的配比?3. deep learning 入门和kaggle比赛4. 有些 Kaggle 比赛数据集很大,可能需要更多的 GPU 显存,请推荐显存4. GDDR6和HBM25. HDD 或 SATA SSD1. 基础推荐 假设您作为一个深度学习入门学者的需求,以下是一份推荐的电脑硬件配…...

eNSP-Cloud(实现本地电脑与eNSP内设备之间通信)

说明&#xff1a; 想象一下&#xff0c;你正在用eNSP搭建一个虚拟的网络世界&#xff0c;里面有虚拟的路由器、交换机、电脑&#xff08;PC&#xff09;等等。这些设备都在你的电脑里面“运行”&#xff0c;它们之间可以互相通信&#xff0c;就像一个封闭的小王国。 但是&#…...

业务系统对接大模型的基础方案:架构设计与关键步骤

业务系统对接大模型&#xff1a;架构设计与关键步骤 在当今数字化转型的浪潮中&#xff0c;大语言模型&#xff08;LLM&#xff09;已成为企业提升业务效率和创新能力的关键技术之一。将大模型集成到业务系统中&#xff0c;不仅可以优化用户体验&#xff0c;还能为业务决策提供…...

synchronized 学习

学习源&#xff1a; https://www.bilibili.com/video/BV1aJ411V763?spm_id_from333.788.videopod.episodes&vd_source32e1c41a9370911ab06d12fbc36c4ebc 1.应用场景 不超卖&#xff0c;也要考虑性能问题&#xff08;场景&#xff09; 2.常见面试问题&#xff1a; sync出…...

Mac软件卸载指南,简单易懂!

刚和Adobe分手&#xff0c;它却总在Library里给你写"回忆录"&#xff1f;卸载的Final Cut Pro像电子幽灵般阴魂不散&#xff1f;总是会有残留文件&#xff0c;别慌&#xff01;这份Mac软件卸载指南&#xff0c;将用最硬核的方式教你"数字分手术"&#xff0…...

ip子接口配置及删除

配置永久生效的子接口&#xff0c;2个IP 都可以登录你这一台服务器。重启不失效。 永久的 [应用] vi /etc/sysconfig/network-scripts/ifcfg-eth0修改文件内内容 TYPE"Ethernet" BOOTPROTO"none" NAME"eth0" DEVICE"eth0" ONBOOT&q…...

Python Ovito统计金刚石结构数量

大家好,我是小马老师。 本文介绍python ovito方法统计金刚石结构的方法。 Ovito Identify diamond structure命令可以识别和统计金刚石结构,但是无法直接输出结构的变化情况。 本文使用python调用ovito包的方法,可以持续统计各步的金刚石结构,具体代码如下: from ovito…...

C#学习第29天:表达式树(Expression Trees)

目录 什么是表达式树&#xff1f; 核心概念 1.表达式树的构建 2. 表达式树与Lambda表达式 3.解析和访问表达式树 4.动态条件查询 表达式树的优势 1.动态构建查询 2.LINQ 提供程序支持&#xff1a; 3.性能优化 4.元数据处理 5.代码转换和重写 适用场景 代码复杂性…...

go 里面的指针

指针 在 Go 中&#xff0c;指针&#xff08;pointer&#xff09;是一个变量的内存地址&#xff0c;就像 C 语言那样&#xff1a; a : 10 p : &a // p 是一个指向 a 的指针 fmt.Println(*p) // 输出 10&#xff0c;通过指针解引用• &a 表示获取变量 a 的地址 p 表示…...

MyBatis中关于缓存的理解

MyBatis缓存 MyBatis系统当中默认定义两级缓存&#xff1a;一级缓存、二级缓存 默认情况下&#xff0c;只有一级缓存开启&#xff08;sqlSession级别的缓存&#xff09;二级缓存需要手动开启配置&#xff0c;需要局域namespace级别的缓存 一级缓存&#xff08;本地缓存&#…...

Neko虚拟浏览器远程协作方案:Docker+内网穿透技术部署实践

前言&#xff1a;本文将向开发者介绍一款创新性协作工具——Neko虚拟浏览器。在数字化协作场景中&#xff0c;跨地域的团队常需面对实时共享屏幕、协同编辑文档等需求。通过本指南&#xff0c;你将掌握在Ubuntu系统中使用容器化技术部署该工具的具体方案&#xff0c;并结合内网…...