当前位置: 首页 > 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. 基础推荐 假设您作为一个深度学习入门学者的需求,以下是一份推荐的电脑硬件配…...

React hook之useRef

React useRef 详解 useRef 是 React 提供的一个 Hook&#xff0c;用于在函数组件中创建可变的引用对象。它在 React 开发中有多种重要用途&#xff0c;下面我将全面详细地介绍它的特性和用法。 基本概念 1. 创建 ref const refContainer useRef(initialValue);initialValu…...

前端倒计时误差!

提示:记录工作中遇到的需求及解决办法 文章目录 前言一、误差从何而来?二、五大解决方案1. 动态校准法(基础版)2. Web Worker 计时3. 服务器时间同步4. Performance API 高精度计时5. 页面可见性API优化三、生产环境最佳实践四、终极解决方案架构前言 前几天听说公司某个项…...

leetcodeSQL解题:3564. 季节性销售分析

leetcodeSQL解题&#xff1a;3564. 季节性销售分析 题目&#xff1a; 表&#xff1a;sales ---------------------- | Column Name | Type | ---------------------- | sale_id | int | | product_id | int | | sale_date | date | | quantity | int | | price | decimal | -…...

uniapp中使用aixos 报错

问题&#xff1a; 在uniapp中使用aixos&#xff0c;运行后报如下错误&#xff1a; AxiosError: There is no suitable adapter to dispatch the request since : - adapter xhr is not supported by the environment - adapter http is not available in the build 解决方案&…...

技术栈RabbitMq的介绍和使用

目录 1. 什么是消息队列&#xff1f;2. 消息队列的优点3. RabbitMQ 消息队列概述4. RabbitMQ 安装5. Exchange 四种类型5.1 direct 精准匹配5.2 fanout 广播5.3 topic 正则匹配 6. RabbitMQ 队列模式6.1 简单队列模式6.2 工作队列模式6.3 发布/订阅模式6.4 路由模式6.5 主题模式…...

论文笔记——相干体技术在裂缝预测中的应用研究

目录 相关地震知识补充地震数据的认识地震几何属性 相干体算法定义基本原理第一代相干体技术&#xff1a;基于互相关的相干体技术&#xff08;Correlation&#xff09;第二代相干体技术&#xff1a;基于相似的相干体技术&#xff08;Semblance&#xff09;基于多道相似的相干体…...

免费数学几何作图web平台

光锐软件免费数学工具&#xff0c;maths,数学制图&#xff0c;数学作图&#xff0c;几何作图&#xff0c;几何&#xff0c;AR开发,AR教育,增强现实,软件公司,XR,MR,VR,虚拟仿真,虚拟现实,混合现实,教育科技产品,职业模拟培训,高保真VR场景,结构互动课件,元宇宙http://xaglare.c…...

(一)单例模式

一、前言 单例模式属于六大创建型模式,即在软件设计过程中,主要关注创建对象的结果,并不关心创建对象的过程及细节。创建型设计模式将类对象的实例化过程进行抽象化接口设计,从而隐藏了类对象的实例是如何被创建的,封装了软件系统使用的具体对象类型。 六大创建型模式包括…...

苹果AI眼镜:从“工具”到“社交姿态”的范式革命——重新定义AI交互入口的未来机会

在2025年的AI硬件浪潮中,苹果AI眼镜(Apple Glasses)正在引发一场关于“人机交互形态”的深度思考。它并非简单地替代AirPods或Apple Watch,而是开辟了一个全新的、日常可接受的AI入口。其核心价值不在于功能的堆叠,而在于如何通过形态设计打破社交壁垒,成为用户“全天佩戴…...

在 Spring Boot 中使用 JSP

jsp&#xff1f; 好多年没用了。重新整一下 还费了点时间&#xff0c;记录一下。 项目结构&#xff1a; pom: <?xml version"1.0" encoding"UTF-8"?> <project xmlns"http://maven.apache.org/POM/4.0.0" xmlns:xsi"http://ww…...