LeetCode刷题系列 -- 523. 连续的子数组和
给你一个整数数组 nums 和一个整数 k ,编写一个函数来判断该数组是否含有同时满足下述条件的连续子数组:
子数组大小 至少为 2 ,且
子数组元素总和为 k 的倍数。
如果存在,返回 true ;否则,返回 false 。
如果存在一个整数 n ,令整数 x 符合 x = n * k ,则称 x 是 k 的一个倍数。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 ,编写一个函数来判断该数组是否含有同时满足下述条件的连续子数组:子数组大小 至少为 2 ,且子数组元素总和为 k 的倍数。如果存在,返回 true ;否则,返回 false 。如果存…...
LeetCode刷题系列 -- 525. 连续数组
给定一个二进制数组 nums , 找到含有相同数量的 0 和 1 的最长连续子数组,并返回该子数组的长度。示例 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.创建自定义拦截器,实现 HandlerInterceptor 接口并重写 preHandle(执行具体方法之前的预处理)方法 1.3.2.将自定义拦…...
centos7.6 设置防火墙
1、查看系统版本 cat /etc/redhat-release2、查看防火墙运行状态 systemctl status firewalld这里可以看到当前是未运行状态(inactive)。 3、关闭开机自启动防火墙 systemctl disable firewalld.service4、启动防火墙并查看状态,系统默认 22 端口是开启的。 sy…...
在线支付系列【22】微信支付实战篇之集成服务商API
有道无术,术尚可求,有术无道,止于术。 文章目录前言1. 环境搭建2. 特约商户进件3. 统一下单总结前言 在上篇文档中,我们做好了接入前准备工作,接下来使用开源框架集成服务商相关API。 一个简单的支付系统完成支付流程…...
3.2 埃尔米特转置
定义 对于复矩阵,转置又不一样,常见的操作是共轭转置,也叫埃尔米特转置Hermitian transpose。埃尔米特转置就是对矩阵先共轭,再转置,一般来说用三种符号表示埃尔米特转置: 第一种符号是AHA^HAH,…...
Python爬虫之Scrapy框架系列(13)——实战ZH小说爬取数据入MySql数据库
目录:1 数据持久化存储,写入Mysql数据库①定义结构化字段:②重新编写爬虫文件:③编写管道文件:④辅助配置(修改settings.py文件):⑤navicat创库建表:⑥ 效果如下…...
MySQL篇02-三大范式,多表查询
数据入库时,由于数据设计不合理,会存在数据重复、更新插入异常等情况, 故数据库中表的设计遵循的设计规范:三大范式1.第一范式(1NF)要求数据库的每一列都是不可分割的原子数据项,即原子性。强调的是列的原子性,即数据库中每一列的…...
vue-cli3创建Vue项目
文章目录前言一、使用vue-cli3创建项目1.检查当前vue的版本2.下载并安装Vue-cli33.使用命令行创建项目二、关于配置前言 本文讲解了如何使用vue-cli3创建属于自己的Vue项目,如果本文对你有所帮助请三连支持博主,你的支持是我更新的动力。 下面案例可供…...
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 文件夹强制约定放置所有布局文件,并以插槽的形式作用在页面中1.在app.vue里面2.component 组件使用Vue < component :is"">Vuex生命周期数据请求useFetchuseAsyncDat…...
Python编程自动化办公案例(1)
作者简介:一名在校计算机学生、每天分享Python的学习经验、和学习笔记。 座右铭:低头赶路,敬事如仪 个人主页:网络豆的主页 目录 前言 一.使用库讲解 1.xlrd 2.xlwt 二.主要案例 1.批量合并 模板如下…...
一站式 Elasticsearch 集群指标监控与运维管控平台
上篇文章写了一下消息运维管理平台,今天带来的是ES的监控和运维平台。目前初创企业,不像大型互联网公司,可以重复的造轮子。前期还是快速迭代试错阶段,方便拿到市场反馈,及时调整自己的战略和产品方向。让自己活下去&a…...
C# 调用Python
一、简介 IronPython 是一种在 NET 和 Mono 上实现的 Python 语言,由 Jim Hugunin(同时也是 Jython 创造者)所创造。 Python是一种跨平台的计算机程序设计语言。 是一个高层次的结合了解释性、编译性、互动性和面向对象的脚本语言。 Python是…...
51单片机最强模块化封装(3)
文章目录 前言一、创建smg文件,添加smg文件路径二、smg文件编写三、模块化测试总结前言 本篇文章将带大家继续封装我们的代码。 这里我们会封装数码管的操作函数。 一、创建smg文件,添加smg文件路径 这里的操作就不过多解释了,大家自行看前面的文章即可。 51单片机模块化…...
【CSS 布局】水平垂直居中
CSS 布局-水平垂直居中 一、水平居中 创建一个父盒子,和子盒子 <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丢失消息分为如下几种情况: 生产者丢消息: 生产者将数据发送到RabbitMQ的时候,可能在传输过程中因为网络等问题而将数据弄丢了。 RabbitMQ自己丢消息: 如果没有开启RabbitMQ的持久化&#x…...
十四、Linux网络:高级IO
目录 五种IO模型 同步IO 阻塞IO 非阻塞IO 信号驱动IO IO多路转接 异步IO...
[特殊字符] 智能合约中的数据是如何在区块链中保持一致的?
🧠 智能合约中的数据是如何在区块链中保持一致的? 为什么所有区块链节点都能得出相同结果?合约调用这么复杂,状态真能保持一致吗?本篇带你从底层视角理解“状态一致性”的真相。 一、智能合约的数据存储在哪里…...
HTML 语义化
目录 HTML 语义化HTML5 新特性HTML 语义化的好处语义化标签的使用场景最佳实践 HTML 语义化 HTML5 新特性 标准答案: 语义化标签: <header>:页头<nav>:导航<main>:主要内容<article>&#x…...
【HarmonyOS 5.0】DevEco Testing:鸿蒙应用质量保障的终极武器
——全方位测试解决方案与代码实战 一、工具定位与核心能力 DevEco Testing是HarmonyOS官方推出的一体化测试平台,覆盖应用全生命周期测试需求,主要提供五大核心能力: 测试类型检测目标关键指标功能体验基…...
条件运算符
C中的三目运算符(也称条件运算符,英文:ternary operator)是一种简洁的条件选择语句,语法如下: 条件表达式 ? 表达式1 : 表达式2• 如果“条件表达式”为true,则整个表达式的结果为“表达式1”…...
渲染学进阶内容——模型
最近在写模组的时候发现渲染器里面离不开模型的定义,在渲染的第二篇文章中简单的讲解了一下关于模型部分的内容,其实不管是方块还是方块实体,都离不开模型的内容 🧱 一、CubeListBuilder 功能解析 CubeListBuilder 是 Minecraft Java 版模型系统的核心构建器,用于动态创…...
vue3 字体颜色设置的多种方式
在Vue 3中设置字体颜色可以通过多种方式实现,这取决于你是想在组件内部直接设置,还是在CSS/SCSS/LESS等样式文件中定义。以下是几种常见的方法: 1. 内联样式 你可以直接在模板中使用style绑定来设置字体颜色。 <template><div :s…...
【碎碎念】宝可梦 Mesh GO : 基于MESH网络的口袋妖怪 宝可梦GO游戏自组网系统
目录 游戏说明《宝可梦 Mesh GO》 —— 局域宝可梦探索Pokmon GO 类游戏核心理念应用场景Mesh 特性 宝可梦玩法融合设计游戏构想要素1. 地图探索(基于物理空间 广播范围)2. 野生宝可梦生成与广播3. 对战系统4. 道具与通信5. 延伸玩法 安全性设计 技术选…...
学校时钟系统,标准考场时钟系统,AI亮相2025高考,赛思时钟系统为教育公平筑起“精准防线”
2025年#高考 将在近日拉开帷幕,#AI 监考一度冲上热搜。当AI深度融入高考,#时间同步 不再是辅助功能,而是决定AI监考系统成败的“生命线”。 AI亮相2025高考,40种异常行为0.5秒精准识别 2025年高考即将拉开帷幕,江西、…...
面向无人机海岸带生态系统监测的语义分割基准数据集
描述:海岸带生态系统的监测是维护生态平衡和可持续发展的重要任务。语义分割技术在遥感影像中的应用为海岸带生态系统的精准监测提供了有效手段。然而,目前该领域仍面临一个挑战,即缺乏公开的专门面向海岸带生态系统的语义分割基准数据集。受…...
scikit-learn机器学习
# 同时添加如下代码, 这样每次环境(kernel)启动的时候只要运行下方代码即可: # Also add the following code, # so that every time the environment (kernel) starts, # just run the following code: import sys sys.path.append(/home/aistudio/external-libraries)机…...
