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

LeetCode刷题系列 -- 523. 连续的子数组和

给你一个整数数组 nums 和一个整数 k ,编写一个函数来判断该数组是否含有同时满足下述条件的连续子数组:

  • 子数组大小 至少为 2 ,且

  • 子数组元素总和为 k 的倍数。

如果存在,返回 true ;否则,返回 false

如果存在一个整数 n ,令整数 x 符合 x = n * k ,则称 xk 的一个倍数。0 始终视为 k 的一个倍数。

示例 1:

输入:nums = [23,2,4,6,7], k = 6

输出:true

解释:[2,4] 是一个大小为 2 的子数组,并且和为 6 。

示例 2:

输入:nums = [23,2,6,4,7], k = 6

输出:true

解释:[23, 2, 6, 4, 7] 是大小为 5 的子数组,并且和为 42 。

42 是 6 的倍数,因为 42 = 7 * 6 且 7 是一个整数。

示例 3:

输入:nums = [23,2,6,4,7], k = 13

输出:false

523. 连续的子数组和 - 力扣(Leetcode)

思路

定义前缀和 数组 preSum, preSum[ i ] 表示 nums[0, ..., i] 的和,若是有子数组 nums[i, ..., j] 和是 k的倍数,那么有 ( preSum[j] - preSum[i] ) % k == 0 ,即两者除以k后的余数是相等的。 preSum[j] % k == preSum[i] % k。
我们定义一个 map, key为当前前缀和的余数,即 key = preSum[i] % k
若是有前缀和preSum[j] % k == preSum[i] % k 且 j - i >= 2 ,说明存在子数组 nums[i+1,..., j] 的和为 k的倍数。
这里要考虑一下特殊情况,当preSum[i] % k == 0 ,即前缀和nums[0, ..., i] 本身就是 k的倍数,若是 i >=1 即子数组的长度大于等于 2

c++

class Solution {
public:vector<int> preSum;map<int, vector<int>> targetMap; // key is preSum[ i ]%k, value is ibool checkSubarraySum(vector<int>& nums, int k) {preSum = vector<int>(nums.size(), 0);for(int i = 0; i < nums.size(); i++) {if(i == 0) {preSum[i] = nums[i];} else {preSum[i] = preSum[i-1] + nums[i];}int key = preSum[i] % k;if(key == 0 && i>=1) { // 若是从下标 0 开始的前缀和 preSum[i] 满足是 k的倍数且子数组长度大于2,那么题目中要求的子数组我们是可以满足的,子数组就是 nums[0, ..., i]return true;}if(targetMap.count(key)) {for(auto v:targetMap[key]) {if(i-v>=2) {return true;} else {targetMap[key].push_back(i);}}} else {vector<int> vec;vec.push_back(i);targetMap[key] = vec;}}return false;}
};

相关文章:

LeetCode刷题系列 -- 523. 连续的子数组和

给你一个整数数组 nums 和一个整数 k &#xff0c;编写一个函数来判断该数组是否含有同时满足下述条件的连续子数组&#xff1a;子数组大小 至少为 2 &#xff0c;且子数组元素总和为 k 的倍数。如果存在&#xff0c;返回 true &#xff1b;否则&#xff0c;返回 false 。如果存…...

LeetCode刷题系列 -- 525. 连续数组

给定一个二进制数组 nums , 找到含有相同数量的 0 和 1 的最长连续子数组&#xff0c;并返回该子数组的长度。示例 1:输入: nums [0,1]输出: 2说明: [0, 1] 是具有相同数量 0 和 1 的最长连续子数组。示例 2:输入: nums [0,1,0]输出: 2说明: [0, 1] (或 [1, 0]) 是具有相同数…...

JavaEE15-Spring Boot统一功能处理

目录 1.统一用户登录权限效验 1.1.最初用户登录验证 1.2.Spring AOP用户统一登录验证的问题 1.3.Spring拦截器 1.3.1.创建自定义拦截器&#xff0c;实现 HandlerInterceptor 接口并重写 preHandle&#xff08;执行具体方法之前的预处理&#xff09;方法 1.3.2.将自定义拦…...

centos7.6 设置防火墙

1、查看系统版本 cat /etc/redhat-release2、查看防火墙运行状态 systemctl status firewalld这里可以看到当前是未运行状态(inactive)。 3、关闭开机自启动防火墙 systemctl disable firewalld.service4、启动防火墙并查看状态&#xff0c;系统默认 22 端口是开启的。 sy…...

在线支付系列【22】微信支付实战篇之集成服务商API

有道无术&#xff0c;术尚可求&#xff0c;有术无道&#xff0c;止于术。 文章目录前言1. 环境搭建2. 特约商户进件3. 统一下单总结前言 在上篇文档中&#xff0c;我们做好了接入前准备工作&#xff0c;接下来使用开源框架集成服务商相关API。 一个简单的支付系统完成支付流程…...

3.2 埃尔米特转置

定义 对于复矩阵&#xff0c;转置又不一样&#xff0c;常见的操作是共轭转置&#xff0c;也叫埃尔米特转置Hermitian transpose。埃尔米特转置就是对矩阵先共轭&#xff0c;再转置&#xff0c;一般来说用三种符号表示埃尔米特转置&#xff1a; 第一种符号是AHA^HAH&#xff0c…...

Python爬虫之Scrapy框架系列(13)——实战ZH小说爬取数据入MySql数据库

目录&#xff1a;1 数据持久化存储&#xff0c;写入Mysql数据库①定义结构化字段&#xff1a;②重新编写爬虫文件&#xff1a;③编写管道文件&#xff1a;④辅助配置&#xff08;修改settings.py文件&#xff09;&#xff1a;⑤navicat创库建表&#xff1a;⑥ 效果如下&#xf…...

MySQL篇02-三大范式,多表查询

数据入库时,由于数据设计不合理&#xff0c;会存在数据重复、更新插入异常等情况, 故数据库中表的设计遵循的设计规范&#xff1a;三大范式1.第一范式(1NF)要求数据库的每一列都是不可分割的原子数据项&#xff0c;即原子性。强调的是列的原子性&#xff0c;即数据库中每一列的…...

vue-cli3创建Vue项目

文章目录前言一、使用vue-cli3创建项目1.检查当前vue的版本2.下载并安装Vue-cli33.使用命令行创建项目二、关于配置前言 本文讲解了如何使用vue-cli3创建属于自己的Vue项目&#xff0c;如果本文对你有所帮助请三连支持博主&#xff0c;你的支持是我更新的动力。 下面案例可供…...

Linux perf probe 的使用(三)

文章目录前言一、Dynamic Tracing二、kprobes2.1 perf kprobe 的使用2.2 kprobe Arguments3.3 tcp_sendmsg()3.3.1 Kernel: tcp_sendmsg()3.3.2 Kernel: tcp_sendmsg() with size3.3.2 Kernel: tcp_sendmsg() line number and local variable三、uprobes的使用3.1 perf uprobe …...

python GUI编程 多窗口跳转

# 多窗口跳转例子from tkinter import *def main(): # 主窗体def goto(num):root.destroy() # 关闭主窗体if num 1:one() # 进入第1个窗体elif num 2:two() # 进入第2个窗体root Tk()root.geometry(300x150600200)root.title(登录窗口)but1 Button(root, text"进入…...

nuxt 学习笔记

这里写目录标题路由跳转NuxtLinkquery参数params参数嵌套路由tab切换效果layouts 文件夹强制约定放置所有布局文件&#xff0c;并以插槽的形式作用在页面中1.在app.vue里面2.component 组件使用Vue < component :is"">Vuex生命周期数据请求useFetchuseAsyncDat…...

Python编程自动化办公案例(1)

作者简介&#xff1a;一名在校计算机学生、每天分享Python的学习经验、和学习笔记。 座右铭&#xff1a;低头赶路&#xff0c;敬事如仪 个人主页&#xff1a;网络豆的主页​​​​​​ 目录 前言 一.使用库讲解 1.xlrd 2.xlwt 二.主要案例 1.批量合并 模板如下&#xf…...

一站式 Elasticsearch 集群指标监控与运维管控平台

上篇文章写了一下消息运维管理平台&#xff0c;今天带来的是ES的监控和运维平台。目前初创企业&#xff0c;不像大型互联网公司&#xff0c;可以重复的造轮子。前期还是快速迭代试错阶段&#xff0c;方便拿到市场反馈&#xff0c;及时调整自己的战略和产品方向。让自己活下去&a…...

C# 调用Python

一、简介 IronPython 是一种在 NET 和 Mono 上实现的 Python 语言&#xff0c;由 Jim Hugunin&#xff08;同时也是 Jython 创造者&#xff09;所创造。 Python是一种跨平台的计算机程序设计语言。 是一个高层次的结合了解释性、编译性、互动性和面向对象的脚本语言。 Python是…...

51单片机最强模块化封装(3)

文章目录 前言一、创建smg文件,添加smg文件路径二、smg文件编写三、模块化测试总结前言 本篇文章将带大家继续封装我们的代码。 这里我们会封装数码管的操作函数。 一、创建smg文件,添加smg文件路径 这里的操作就不过多解释了,大家自行看前面的文章即可。 51单片机模块化…...

【CSS 布局】水平垂直居中

CSS 布局-水平垂直居中 一、水平居中 创建一个父盒子&#xff0c;和子盒子 <div class"parent"><div class"child"></div> </div>基本样式如下 .parent {background-color: #fff; }.child {background-color: #999;width: 100p…...

【C++】类和对象--类的6个默认成员函数

目录1.类的6个默认成员函数2.构造函数2.1概念2.2特性3.析构函数3.1概念3.2特性4.拷贝构造函数4.1概念4.2特征5.赋值运算符重载5.1运算符重载5.2赋值运算符重载5.3前置和后置重载5.4流插入和流提取运算符重载6.const成员7.取地址重载和const取地址操作符重载1.类的6个默认成员函…...

常见面试题---------如何处理MQ消息丢失的问题?

如何处理MQ消息丢失的问题? RabbitMQ丢失消息分为如下几种情况&#xff1a; 生产者丢消息&#xff1a; 生产者将数据发送到RabbitMQ的时候&#xff0c;可能在传输过程中因为网络等问题而将数据弄丢了。 RabbitMQ自己丢消息&#xff1a; 如果没有开启RabbitMQ的持久化&#x…...

十四、Linux网络:高级IO

目录 五种IO模型 同步IO 阻塞IO 非阻塞IO 信号驱动IO IO多路转接 异步IO...

React 第五十五节 Router 中 useAsyncError的使用详解

前言 useAsyncError 是 React Router v6.4 引入的一个钩子&#xff0c;用于处理异步操作&#xff08;如数据加载&#xff09;中的错误。下面我将详细解释其用途并提供代码示例。 一、useAsyncError 用途 处理异步错误&#xff1a;捕获在 loader 或 action 中发生的异步错误替…...

PHP和Node.js哪个更爽?

先说结论&#xff0c;rust完胜。 php&#xff1a;laravel&#xff0c;swoole&#xff0c;webman&#xff0c;最开始在苏宁的时候写了几年php&#xff0c;当时觉得php真的是世界上最好的语言&#xff0c;因为当初活在舒适圈里&#xff0c;不愿意跳出来&#xff0c;就好比当初活在…...

基于服务器使用 apt 安装、配置 Nginx

&#x1f9fe; 一、查看可安装的 Nginx 版本 首先&#xff0c;你可以运行以下命令查看可用版本&#xff1a; apt-cache madison nginx-core输出示例&#xff1a; nginx-core | 1.18.0-6ubuntu14.6 | http://archive.ubuntu.com/ubuntu focal-updates/main amd64 Packages ng…...

YSYX学习记录(八)

C语言&#xff0c;练习0&#xff1a; 先创建一个文件夹&#xff0c;我用的是物理机&#xff1a; 安装build-essential 练习1&#xff1a; 我注释掉了 #include <stdio.h> 出现下面错误 在你的文本编辑器中打开ex1文件&#xff0c;随机修改或删除一部分&#xff0c;之后…...

大语言模型如何处理长文本?常用文本分割技术详解

为什么需要文本分割? 引言:为什么需要文本分割?一、基础文本分割方法1. 按段落分割(Paragraph Splitting)2. 按句子分割(Sentence Splitting)二、高级文本分割策略3. 重叠分割(Sliding Window)4. 递归分割(Recursive Splitting)三、生产级工具推荐5. 使用LangChain的…...

【ROS】Nav2源码之nav2_behavior_tree-行为树节点列表

1、行为树节点分类 在 Nav2(Navigation2)的行为树框架中,行为树节点插件按照功能分为 Action(动作节点)、Condition(条件节点)、Control(控制节点) 和 Decorator(装饰节点) 四类。 1.1 动作节点 Action 执行具体的机器人操作或任务,直接与硬件、传感器或外部系统…...

HBuilderX安装(uni-app和小程序开发)

下载HBuilderX 访问官方网站&#xff1a;https://www.dcloud.io/hbuilderx.html 根据您的操作系统选择合适版本&#xff1a; Windows版&#xff08;推荐下载标准版&#xff09; Windows系统安装步骤 运行安装程序&#xff1a; 双击下载的.exe安装文件 如果出现安全提示&…...

Matlab | matlab常用命令总结

常用命令 一、 基础操作与环境二、 矩阵与数组操作(核心)三、 绘图与可视化四、 编程与控制流五、 符号计算 (Symbolic Math Toolbox)六、 文件与数据 I/O七、 常用函数类别重要提示这是一份 MATLAB 常用命令和功能的总结,涵盖了基础操作、矩阵运算、绘图、编程和文件处理等…...

安卓基础(aar)

重新设置java21的环境&#xff0c;临时设置 $env:JAVA_HOME "D:\Android Studio\jbr" 查看当前环境变量 JAVA_HOME 的值 echo $env:JAVA_HOME 构建ARR文件 ./gradlew :private-lib:assembleRelease 目录是这样的&#xff1a; MyApp/ ├── app/ …...

SQL慢可能是触发了ring buffer

简介 最近在进行 postgresql 性能排查的时候,发现 PG 在某一个时间并行执行的 SQL 变得特别慢。最后通过监控监观察到并行发起得时间 buffers_alloc 就急速上升,且低水位伴随在整个慢 SQL,一直是 buferIO 的等待事件,此时也没有其他会话的争抢。SQL 虽然不是高效 SQL ,但…...