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

LeetCode: 523. 连续的子数组和

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

子数组大小 至少为 2 ,且
子数组元素总和为 k 的倍数。
如果存在,返回 true ;否则,返回 false 。

如果存在一个整数 n ,令整数 x 符合 x = n * k ,则称 x 是 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
 

提示:

1 <= nums.length <= 105
0 <= nums[i] <= 109
0 <= sum(nums[i]) <= 231 - 1
1 <= k <= 231 - 1

分析:

       该题最简单的方法,就是枚举满足条件的子数组,时间复杂度为O(N^{2}),然后计算数组的和是否为k的倍数,复杂度为O(N),总的复杂度为O(N^{3})。

       接下来我们对该题进行简化,因为是连续子数组,很容易考虑到是否可以用前缀和的方式。这样只需要我们枚举左右边界即可,时间复杂度为O(N^{2})。

       如果想进一步优化的话,这里用到了一个数学定理:同余定理。我们设sum[i]为前i个数(0, 1, 2, 3, ..., i - 1)的和,那么区间[i, j]的和为sum[j + 1] - sum[i],如果其结果是k的倍数,则有sum[j + 1] - sum[i] = n * k,等式两边分别对k取余,有sum[j + 1] % k - sum[i] % k = 0,即sum[j + 1] % k = sum[i] % k。这就启发我们只需要验证左右两个边界对k取余的结果是否相同。此时引入哈希表,记录不同余数第一次出现(使数组尽可能长,满足对数组长度的要求)的下标。这种情况下时间复杂度为O(N)。

       另外,记录前缀和的时候,我们只需要一个变量sum即可。而在Leetcode官方题解上是这样写的:

int remainder = 0;
remainder = (remainder + nums[i]) % k;/*
简单证明一下:
设remainder(i)为第i次得到的结果
remainder(0) = 0
remainder(1) = (remainder(0) + nums[0]) % k= nums[0] % k
remainder(2) = (remainder(1) + nums[1]) % k= (remainder(1) % k + nums[1] % k) % k(分配律)= (nums[0] % k % k + nums[1] % k) % k= (nums[0] % k + nums[1] % k) % k= (nums[0] + nums[1]) % k(分配律)
remainder(3) = (remainder(2) + nums[2]) % k= (remainder(2) % k + nums[2] % k) % k(分配律)= ((nums[0] + nums[1]) % k % k + nums[2] % k) % k= ((nums[0] + nums[1]) % k + nums[2] % k) % k= (nums[0] + nums[1] + nums[2]) % k(分配律)
以此类推
*/

题解代码如下:

class Solution {
public:bool checkSubarraySum(vector<int>& nums, int k) {int n = nums.size();if(n < 2) return false;unordered_map<int, int> mp;mp[0] = -1;int remainder = 0;for(int i = 0; i < n; i++){remainder = (remainder + nums[i]) % k;if(mp.count(remainder)){int preIndex = mp[remainder];if(i - preIndex >= 2)return true;}else{mp[remainder] = i;}}return false;}
};

 

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.exyb.cn/news/show-3126.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈,一经查实,立即删除!

Linux下安装sqlite3

文章目录前言安装步骤测试安装成功前言 sqlite3的安装 安装步骤 依次执行以下命令&#xff1a; 1)wget http://www.sqlite.org/sqlite-3.5.6.tar.gz 2)tar -xzvf sqlite-3.5.6.tar.gz 3)cd sqlite-3.5.6 4)./configure 5)make 6)make install测试安装成功 出现红色方框信息…...

面向对象的程序语言设计-2021春季学期面向对象程序设计第十四周上机练习#1

Set 描述 现有一整数集&#xff08;允许有重复元素&#xff09;&#xff0c;初始为空。我们定义如下操作&#xff1a; add x 把x加入集合 del x 把集合中所有与x相等的元素删除 ask x 对集合中元素x的情况询问 对每种操作&#xff0c;我们要求进行如下输出。 add 输出操作后集…...

拉伯配资6月1日策略

5月回想&#xff1a;在5月份的战略中&#xff0c;我们认为其时胶着的商场可能在5月会有所改动。从实践表现来看&#xff0c;5月下旬商场明显出现了一些活泼做多的信号&#xff0c;商场也选择了向上打破。上证指数上涨超4%&#xff0c;深圳成指上涨近3%。 行情判别&#xff1a;从…...

词达人自动做题PHP版全套开源+前后台分离开发+带半个软件+CDKey兑换

简介&#xff1a; 开发语言&#xff1a;PHPMysql 源码简介与安装说明&#xff1a; 易语言版的我是今天写的。多线程有需要再去调风控&#xff0c;恶心的一批。我这网课上到现在基本上啥TM也没学。就这样了。我就简单上几张图自己看看吧。前端是Vue.js。后端是PHP。前后台分离…...

在一家公司干多长时间跳槽才合适?最全的BAT大厂面试题整理

本篇文章主要内容 数据缓存 为何要使用缓存 哪类数据适合缓存 缓存的利与弊 如何保证缓存和数据库一致性 不更新缓存&#xff0c;而是删除缓存 先操作缓存&#xff0c;还是先操作数据库 非要保证数据库和缓存数据强一致该怎么办 缓存和数据库一致性实战 实战&#xff…...

前端javascript中Location的使用

标题location的常用方法&#xff1b; location.search.slice(1) // 取url中?之后的部分 location.hash.substring(1) //取url中#之后的部分 通过javascript跳转&#xff1a; location.href() location.assign() location.replace()...

微信小程序趋势及前景,大厂直通车!

最近看到群里看到一个女生&#xff0c;讲述了她从开始选择Android&#xff0c;经过非常努力的学习和挣扎&#xff0c;然而最后面对当前的环境却不得不放弃。看完以后真的非常替她感觉惋惜&#xff0c;如果早几年入行可能结果会比现在好很多&#xff0c;但可惜&#xff0c;这就是…...

LAMP源码编译安装(Apache,Mysql,PHP,论坛安装详解)

目录前言一.LAMP概述1.LAMP架构2.LAMP组件的主要作用二.Apache httpd服务编译安装1.关闭防火墙&#xff0c;将安装Apache所需软件包传到/opt目录下2.安装环境依赖包3.配置软件模块4.编译及安装5.优化配置文件路径&#xff0c;并把httpd服务的可执行程序文件放入路径环境变量的目…...

[Jetson][转载]jetson上安装pytorch+torchvision教程

1. Jetpack默认已安装opencv、cuda、cudnn&#xff0c;故只需再安装pytorch即可&#xff0c;留意jetson是arm架构&#xff0c;需要下载对应的安装文件加以安装  2. pytorch的安装   查询Jetpack的版本 sudo -H pip3 install jetson-stats jetson_release   pytorch的whl文…...

sort在不同浏览器下执行效果

sort在不同浏览器下执行效果 let arr [{name: zhangsan, age: 40},{name: lisi, age: 20},{name: laowang, age: 50},{name: xiaoli, age: 60},{name: xiaojin, age: 30}, ] arr.sort((a, b) > b.age > a.age);上面这段代码在谷歌浏览器中&#xff0c;是不会进行排序的…...

设计模式导读助记

各个设计模式的详细介绍都已经完成&#xff0c;但是不经常用总会忘&#xff0c;所以我想用 一句话 总结设计模式&#xff0c;思考模式的真正意图&#xff0c;再用 一点提示 来思考代码如何实现 写在前面 我整理的设计模式这一个系列&#xff0c;主要是结合了以下几本书 : 《设…...

RT-Thrad|STM32F103+ESP8266 S01+RT-Thread联网之环境搭建(1/3)

文章目录前言硬件准备百问网STM32F103ESP8266 01SESP8266 介绍ESP8266 01S技术规格参数软件准备下载安装 Keil μVision5Pack Installer安装 ST-Link 驱动获取RT-Thread源码下载安装 RT-Thread env 工具文章列表 RT-Thrad|STM32F103ESP8266 S01RT-Thread联网之环境搭建(1/3)RT…...

Flask初体验

Flask初体验 flask框架是一个微型框架&#xff0c;但是微型框架不代表功能比其他框架少&#xff0c;并且flask的约束也比较少&#xff0c;使用更加方便。Flask安装 pip install flask 废话不多说直接上代码 from flask import Flaskapp Flask(__name__)app.route("/&qu…...

天眼查怎么删除信息_天眼查删除信息的方法介绍

天眼查信息怎么删除 天眼查风险信息怎么清除 天眼查问答信息怎么删除 天眼查法律诉讼信息可以删吗 天涯查上的信息删除怎么操作&#xff0c;天眼查成立于2014年&#xff0c;至今发展迅速&#xff0c;已经帮助了无数的企业和消费者&#xff0c;那么很多企业的天眼查信息有时候需…...

5.Random

用于生产一个随机数 步骤&#xff1a; 1.导包 import java.util.Random; 2.创建对象 Random random new Random();3.获取随机数 int number random.nextInt(10); //随机数的取值范围是[0,10),即大于等于&#xff0c;小于10 上面不能获取到10&#xff0c;若要获取到10&…...

Xxl-Job调度器原理解析

项目解析源码地址&#xff1a;https://gitee.com/lidishan/xxl-job-code-analysisxxl-job版本&#xff1a;2.3.0Xxl-Job分为执行器、调度器。而我们平时的客户端就属于一个执行器&#xff0c;执行器启动的时候会自动注册到调度器上&#xff0c;然后调度器进行远程调度。调度器初…...

51单片机利用锁存器控制数码管显示年月日时分秒

数码管模块中的两片74hc573&#xff0c;一片锁存段码&#xff0c;一片锁存位码&#xff0c;这样才能驱动8位数码管。74hc573是锁存器&#xff0c;用于数码管显示时通常是采用段选、片选共用同一组并口的驱动方式。 驱动数码管需要两个信号&#xff0c;一个是段选信号&#xff…...

webrtc之SVC实现(十)

一、概念 SVC&#xff08;可适性视频编码或可分级视频编码&#xff09;是传统H.264/MPEG-4 AVC编码的延伸&#xff0c;可提升更大的编码弹性&#xff0c;并具有时间可适性&#xff08;Temporal Scalability&#xff09;、空间可适性&#xff08;Spatial Scalability&#xff09…...

LeetCode 数值的整数次方

实现 pow(x, n) &#xff0c;即计算 x 的 n 次幂函数&#xff08;即&#xff0c;xn&#xff09;。不得使用库函数&#xff0c;同时不需要考虑大数问题。 示例 1&#xff1a; 输入&#xff1a;x 2.00000, n 10 输出&#xff1a;1024.00000 示例 2&#xff1a; 输入&#xf…...

python 继承和多态

在已有类的基础上创建新类&#xff0c;这其中的一种做法就是让一个类从另一个类那里将属性和方法直接继承下来&#xff0c;从而减少重复代码的编写。提供继承信息的我们称之为父类&#xff0c;也叫超类或基类&#xff1b;得到继承信息的我们称之为子类&#xff0c;也叫派生类或…...

成熟销售8个促单技巧 学会推着客户往前走

听说三孩政策来了&#xff0c;感觉身上的担子又重了有没有&#xff1f;不赶紧多点成单赚钱&#xff0c;怎么养得起三孩。做销售收入上限还是相对较高的&#xff0c;只要客户撩的好&#xff0c;大单子一开&#xff0c;提成收入就蹭蹭蹭地上去了。 开大单、多开单&#xff0c;都离…...

etcd学习和实战:1、etcd了解、安装和应用场景

etcd学习和实战&#xff1a;1、etcd了解、安装和应用场景 文章目录etcd学习和实战&#xff1a;1、etcd了解、安装和应用场景1. 前言2. etcd资料和总结说明2.1 什么是etcd2.2 相关资料3. Ubuntu安装etcd3.1 安装go3.2 安装etcd3.3 启动etcd3.4 测试etcd&#xff08;设置并获取ke…...

CSS四种定位方式的详解,含BATJM大厂

开始 我大学读的是大专&#xff0c;在学校学的是机电一体化。临近毕业的时候选择了学习web前端技术&#xff0c;因为做机电实在又累工资又低&#xff0c;而我更喜欢坐办公室的工作&#xff0c;有空调吹&#xff0c;我很现实&#xff0c;就是想多赚一点钱。到现在做了两年前端的…...

Windows环境下安装RocketMQ

一.预备环境 1.系统 Windows 2. 环境 JDK1.8、Maven、Git 二. RocketMQ部署 1.下载 1.1地址&#xff1a;http://rocketmq.apache.org/release_notes/release-notes-4.3.0/ 1.2选择‘Binary’进行下载 1.3解压已下载工程 2. 配置 2.1 系统环境变量配置 变量名&#xff1a;ROC…...

Mybatis-plus学习笔记

笔记整理于狂神说Mybatis-plus Mybatis-Plus学习笔记 文章目录笔记整理于狂神说Mybatis-plusMybatis-Plus学习笔记1、简介1.1、特性1.2、支持数据库1.3、框架结构2、快速入门2.1、创建数据库2.2、创建数据表2.3、创建项目2.4、导入依赖2.5、连接数据库2.6、代码编写3、配置日志…...

思鑫诚禾讲教资备考时间和精力

上半年的教师资格证考试已经结束了&#xff0c;有些没有报名上错过的同学就要积极准备下半年的教师资格证考试了&#xff0c;那同学们应该怎样准备自己的备考时间呢&#xff1f;接下来就和思鑫诚禾教育一起了解一下我们应该把主要的精力放在哪里。 在我们的综合素质备考中&…...

mysql事务

mysql事务四大特性 1.原子性 理解&#xff1a;事务中的所有操作要么全部一起执行&#xff0c;要么在发生的错误的时候全部不执行&#xff0c;也就是事务回滚了 原理&#xff1a;mysql使用undo log逻辑日志进行回滚&#xff0c;mysql会生成redo log和undo log 文件&#xff0c;u…...

Ambari2.7.3集群Oozie调度Spark示例

文章目录1.环境准备2.修改配置文件2.1 解压Oozie自带样例包2.2 修改workflow.xml文件2.3 修改job.properties文件3.上传到HDFS4.提交任务5.监控1.环境准备 集群版本&#xff1a;Ambari2.7.3 HDP3.0.1.0-187集群开启Kerberos身份认证&#xff0c;Ranger权限认证 2.修改配置文…...

词达人自动做题PHP版全套开源+前后台分离开发+带半个软件+CDKey兑换

简介&#xff1a; 开发语言&#xff1a;PHPMysql 源码简介与安装说明&#xff1a; 易语言版的我是今天写的。多线程有需要再去调风控&#xff0c;恶心的一批。我这网课上到现在基本上啥TM也没学。就这样了。我就简单上几张图自己看看吧。前端是Vue.js。后端是PHP。前后台分离…...

笔记:svn操作优化,在bash中通过别名实现svn代码仓库的在线操作

一、TortoiseSVN 使用过SVN的应该都知道TortoiseSVN&#xff0c;界面操作简单方便&#xff0c;易上手。 二、SVN命令行 如果想在命令行中操作代码仓库&#xff0c;必须把代码下下来&#xff0c;才能在目录间切换&#xff0c;如果代码仓库中的代码量很大&#xff0c;全部下下…...

西邮Linux兴趣小组2019纳新试题总结

1.下面代码段将打印出多少个’’&#xff1f;运用相关知识解释该输出。 int main() {for(unsigned int i3;i>0;i--){putchar();} }无数个&#xff0c;因为无符号数无负&#xff0c;造成死循环。2.下列三种交换整数的方式是如何实现交换的&#xff1f; /*(1)*/ int c a ; …...

西邮计算机网络实验,西邮网络实验报告.doc

西邮网络实验报告RIP实验环境&#xff1a;实验步骤&#xff1a;在pocket tracer中搭建实验环境。为各端口分配IP地址(合理分配4个子网即可)分别为路由器各有效端口配置IP如&#xff1a;R0(config)#int fa 0/1R0(config-if)#ip address 192.168.1.1 255.255.255.0R0(config-if)#…...

西邮linux兴趣小组2019-2021三年纳新试题浅析

西邮linux兴趣小组2019-2021三年纳新试题浅析西邮 Linux 兴趣小组 2019 纳新试题西邮 Linux 兴趣小组 2020 纳新试题西邮 Linux 兴趣小组 2021 纳新试题关于纳新试题&#xff0c;您需要了解&#xff1a; 本题仅作为面试有限参考为了代码的简洁,略去了大部分不影响理解的预处理…...

2021西邮linux兴趣小组纳新题解

目录1. 请试着解释其输出2. 下面代码的运行输出结果是什么&#xff0c;并说说你的理解。3. 这段代码的输出结果是什么&#xff1f;为什么会出现这样的结果&#xff1f;4. 下面程序会出现什么结果&#xff1f;为什么会出现这样的结果&#xff1f;5. 下面代码的运行输出结果是什么…...

西邮Linux兴趣小组2022纳新面试题题解

本题目只作为Xiyou Linux兴趣小组2022纳新面试的有限参考。为节省版面&#xff0c;本试题的程序源码省去了#include指令。本试题中的程序源码仅用于考察C语言基础&#xff0c;不应当作为C语言「代码风格」的范例。题目难度随机排列。 所有题目编译并运行于x86_64 GNU/Linux环境…...

西邮Linux兴趣小组面试题总结(2020)

面试题总结 宏定义 #define 标识符 字符串 2019年面试题 下面代码段的输出结果是什么&#xff1f;输出该结果的原因是&#xff1f; #define X a b int main(int argc, char *argv[]) {int a 1, b 1;printf("%d\n", X * X);return 0; } 代码相当于 int main(in…...

西邮杯acm试题

—明天c语言机试赶紧花一天时间把西邮杯写下练练手… 写的脖子痛… 问题&#xff1a;可逆素数 题目描述 若将某一素数的个位数字顺序颠倒后得到的数任然是素数&#xff0c;则此素数称为可逆素数 判断给定的n个数据是否是可逆素数。 输入 第一行为n值&#xff0c;第二行输…...

西邮计算机学院楚东方,西邮计算机系课堂教学质量监控办法.doc

计算机学院本科课堂教学质量监控办法? ?课堂教学是整个教育、教学过程的最主要环节&#xff0c;加强课堂教学质量监控是全面提高教学质量的关键&#xff0c;同时对保证本学院正常教学秩序&#xff0c;树立良好教风、学风&#xff0c;培养全面发展的高素质人才具有重要意义。为…...

西邮Linux兴趣小组2020纳新试题

第一题&#xff1a; 运行下面的代码&#xff0c;输出结果是什么&#xff0c;请解释说明&#xff1a; #include<stdio.h> int i; int main(int argc, char *argv[]) {i--;if (i > sizeof(i)){printf(">\n");}else{printf("<\n");}return 0…...

考研院校(转载自西邮学子)

考研院校&#xff08;转载自西邮学子&#xff09; 学了两年多的嵌入式&#xff0c;最后还是决定继续深造继续提升自己&#xff0c;手上的项目也应该是大学本科阶段最后一个项目了&#xff0c;周围的同学面试的面试&#xff0c;考研的考研&#xff0c;我拖到现在才开始准备考研…...

西邮Linux兴趣小组2021纳新面试题

#include<stdio.h> #include<string.h> int main(void) {char s[]"I love Linux\0\0\0";int asizeof(s);//16int bstrlen(s);//12printf("a%d b%d\n",a,b);return 0; } sizeof是一个运算符&#xff0c;求的是数据类型所占空间的大小&#xf…...

西邮Linux2020年面试题

西邮Linux2020年面试题1运行下面代码&#xff0c;输出结果是什么&#xff1f;解释其原因。2执行下面代码段&#xff0c;谈谈你对宏的理解。3分析下面程序的输出结果4在程序中执行此函数&#xff0c;其输出结果是什么&#xff0c;在同一程序中执行多次该函数&#xff0c;输出结果…...

西邮课设

课程设计第一天 环境配置 python环境配置 VNC远程控制桌面 安装ipython python -m pip install --upgrade pip升级pip安装工具pip install ipython测试&#xff1a;在命令行输入ipython 编辑器 安装jupyter pip install jupyter 开发 新建项目后进入cmd命令行 cd到项目…...

西邮linux兴趣小组网络,西邮Linux兴趣小组2012纳新笔试题

这是我们西邮Linux兴趣小组2012的纳新笔试题&#xff0c;对于大一的学生&#xff0c;出得有难度哦&#xff0c;个人感觉比腾讯实习生的笔试题出的有水平。西邮Linux兴趣小组纳新试题姓名&#xff1a; 院系&#xff1a; 班级&#xf…...

西邮导航

package xiyouNavigationCode;import java.awt.BorderLayout; import java.awt.Color; import java.awt.Container; import java.awt.Dimension; import java.awt.FlowLayout; import java.awt.Font; import java.awt.Frame; import java.awt.GridLayout; import java.awt.Ima...

西邮linux兴趣小组网络,西邮Linux兴趣小组纳新笔试试题

下面是西邮Linux小组今年纳新的笔试试题&#xff0c;原文在这里。1、 下面这个程序的输出结果是什么&#xff1f;int main(){ int a (1, 2);printf(“a %d\n”, a);return 0;}解答&#xff1a;a 2这里利用了逗号表达式。2、下面这个程序的输出结果是什么&#xff1f;struct …...

西邮计算机网络实验,2018ThoughtWorks西邮实验室纳新题

第一部分 概念题1.html基本结构和常见标签(三个以上)2.谈谈你对css盒模型的理解 (最好举个例子)3.css一共有几种设置样式的方式&#xff0c;分别是什么&#xff0c;优先级如何4.html5有哪些新特性(三个以上)&#xff0c;谈谈你对html语义化是怎样理解的5.display有哪些值&#…...

西邮linux兴趣小组网络,西邮Linux兴趣小组

本次技术分享由小组16级成员刘生玺同学主持&#xff0c;主题为“Linux Shell”&#xff0c;大家可以通过文末链接下载本期技术分享的PPT。我们欢迎所有17级的小鲜肉和所有对这方面感兴趣的同学参加这次技术分享&#xff0c;与我们一起探讨交流&#xff0c;相互学习&#xff0c;…...

西邮Linux兴趣小组2017-2019纳新题题解

目录2017201820192017 1. 分析下列程序的输出。 int main(int argc, char *argv[]) { int t 4; printf("%lu\n", sizeof(t--)); printf("%lu\n", sizeof("ab c\nt\012\xa1*2")); return 0; }输出&#xff1a; 4 11 sizeof()返回操作数占用内存…...

西邮Linux兴趣小组2019-2021年纳新面试题解析

目录 2019年 2020年 2021年 2019年 1、 ​ 结果&#xff1a;无限打印“ ” 大家都知道在码长为16位的情况下&#xff0c;int 的取值范围为-32768&#xff5e;32767,而unsinged int即无符号整形的范围为0&#xff5e;65535。 那么问题来了哈&#xff0c;unsigned int类型…...