leetcode523. 连续的子数组和python_哈希表和前缀和

news/2024/3/29 14:55:12/文章来源:https://blog.csdn.net/xuranyi/article/details/128091282

题目

给你一个整数数组 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

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

思路和代码

这题我用了回溯用了暴力用了哈希和前缀和,都没有通过,我怎么那么优秀啊。

首先暴力很好想,就是枚举所有长度大于2的连续子数组,在判断一下是否满足条件,这很好写啊,超时。

回溯其实本质也就是暴力,但对于连续子数组的回溯(现在不会)我没写出来,写的有点问题,只能从第一个数开始试探情况。

最后看到了题目提示的关键词哈希表和前缀和,这我熟啊。但是不知道具体怎么用,就算求得到前缀和,那怎么得到不同连续子数组的情况,不还是要两层for循环遍历么?好的,吭哧吭哧写出来,调调调,漂亮,还是超时。

放弃,看别人的题解,太优秀了。

首先,这里面有一个一个概念——同余定理:

当两个数除以某个数的余数相等,那么二者相减后肯定可以被该数整除。

所以,哈希表怎么用?key是前缀和对k的余数,value是当前值的索引。(这谁啊,怎么那么聪明啊)

总体思路就是遍历数组,先求前缀和,然后求余res,判断余数是不是已经在字典dic中,且dic[res]和当前的索引i相差大于等于2,是则返回True。否则,注意,要判断余数在不在dic中,不在的话dic[res]=i。

为什么要多判断在不在,而不是直接赋值?

因为有种情况如[5,0,0,0],k=3。如果直接赋值,dic[2]前后等于0,1,2,本来后面三个0满足条件的,但这样一写,结果就会返回False。

此外,还有一种情况就是当前前缀和对k取余等于0,可以在for循环的时候判断一下,也可以在一开始的时候加入0:-1。

代码:

class Solution:def checkSubarraySum(self, nums: List[int], k: int) -> bool:# 前缀和 # 哈希表中 key是余数 value是下标# 对nums进行遍历,一边求前缀和,一边求余数# 判断余数是否已经在dic中 在的话 比较当前索引和dic[余数]相差是否大于等于2# 逻辑漏洞5,0,0,0 k=3 5,5,5,5 2对应的value一直在变 结果返回falsedic = {0:-1}pre = 0for i in range(len(nums)):pre += nums[i]res = pre % k# 前i个数正好整除k 要么在这写一个判断句 要么在初始时加0:-1# if res == 0:#     return Trueif res in dic and i - dic[res] >=2:return True#加入这样的一个判断句 如果2已经存在 不改变其值if res not in dic:dic[res] = ireturn False

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

如若内容造成侵权/违法违规/事实不符,请联系dt猫网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

Vue.js 加入高德地图的实现方法

一、功能需求 1.根据输入内容进行模糊查询&#xff0c;选择地址后在地图上插上标记&#xff0c;并更新经纬度坐标显示 2.在地图点击后&#xff0c;根据回传的左边更新地址信息和坐标显示 二、准备 1.申请高德地图账号&#xff0c;创建应用 2.在应用管理中 获得key 和安全密…

[附源码]Python计算机毕业设计Django常见Web漏洞对应POC应用系统

项目运行 环境配置&#xff1a; Pychram社区版 python3.7.7 Mysql5.7 HBuilderXlist pipNavicat11Djangonodejs。 项目技术&#xff1a; django python Vue 等等组成&#xff0c;B/S模式 pychram管理等等。 环境需要 1.运行环境&#xff1a;最好是python3.7.7&#xff0c;…

Python学习:json对象与string相互转换教程

首先要明确&#xff0c;python里有json这个库&#xff0c;但并没有json这个类&#xff0c;所以所谓的json对象本质上就是一个dict&#xff1b;而json这个库&#xff0c;用于实现dict到string、string到dict的互转。 更具体一点&#xff0c;json对象&#xff08;dict&#xff0…

Linux网络编程——IO多路复用

文章目录1&#xff0c;I/O模型2&#xff0c;阻塞I/O 模式2.1&#xff0c;读阻塞&#xff08;以read函数为例&#xff09;2.2&#xff0c;写阻塞3&#xff0c;非阻塞I/O模式3.1&#xff0c;非阻塞I/O模式的实现&#xff08;fcntl()函数、ioctl() 函数&#xff09;3.1.1&#xff…

leetcode 343. 整数拆分(动态规划)

题目链接&#xff1a;343. 整数拆分 动态规划 (1) 确定 dpdpdp 数组下标含义&#xff1a; dp[i]dp[i]dp[i]: 将 iii 拆分为至少两个正整数之后的最大乘积&#xff1b; (2) 确定递推公式&#xff1a; 当 i≥2i \ge 2i≥2 时, 设 jjj 是 iii 拆分出来的第一个正整数&#xff0c…

关于uni-app小程序接入微信登录

https://uniapp.dcloud.net.cn/api/plugins/login.html#login 官网上有关于uni.login()的说明&#xff0c;如果是要微信登录&#xff0c;则需要wx.login()。 小程序登录 | 微信开放文档 如下图&#xff0c;在小程序管理平台生成AppSecret&#xff0c;同时将AppId在HubilderX中…

swift @State @Published @ObservedObject sink

State struct ContentView: View {State private var isRain truevar body: some View {VStack {Image(systemName: isRain ? "cloud.rain.fill" : "sun.max.fill").resizable().frame(width: 100, height: 100)Text(isRain ? "我們淋著大雨不知何…

【PS-7】移动工具

目录 移动工具快捷键【v】&#xff08;英文状态&#xff09; 多文件间拖拽图层对象 快捷键【ALT】复制图层 【ALTSHIFT】只能垂直/水平/45角地去复制图层 4个方向键可以微调图层的位置 变换控件 对齐分布 【题外话】设置参考线颜色 【题外话】快捷键【F12】让已经动过…

实验三-----数据库

一、实验目的 1.掌握SQL Server Management Studio中SQL 查询操作&#xff1b; 2.掌握SQL 的单表查询命令&#xff1b; 3.掌握SQL 的连接查询操作&#xff1b; 4.掌握SQL 的嵌套查询操作&#xff1b; 5.掌握SQL 的集合查询操作。 二、实验环境 1&#xff0e;实验室名称&…

[附源码]计算机毕业设计springboot海南琼旅旅游网

项目运行 环境配置&#xff1a; Jdk1.8 Tomcat7.0 Mysql HBuilderX&#xff08;Webstorm也行&#xff09; Eclispe&#xff08;IntelliJ IDEA,Eclispe,MyEclispe,Sts都支持&#xff09;。 项目技术&#xff1a; SSM mybatis Maven Vue 等等组成&#xff0c;B/S模式 M…

前端单元测试,更进一步

前端测试2022 如果从 2014 年 Jest 的第一个版本发布开始计算&#xff0c;前端开发领域工程化的单元测试能力已经发展了八年有余。Jest 集成了 Jasmine 等以往各种被证明有效的单元测试框架和断言等工具&#xff0c;也可以用来完成包含外部接口服务的集成测试等。最近几年热门的…

xxl-job安装部署

一、简介 XXL-JOB是一个分布式任务调度平台&#xff0c;其核心设计目标是开发迅速、学习简单、轻量级、易扩展。现已开放源代码并接入多家公司线上产品线&#xff0c;开箱即用。 中文文档English Documentation 二、安装 xxl-job需要的提前安装好以下环境&#xff1a;jdk、m…

INTERSPEECH 2022|CALM: 基于对比学习的表现力语音合成跨模态说话风格建模【语音之家】

本文由清华大学与腾讯科技有限公司和香港中文大学合作&#xff0c;并 在腾讯公司落地应用 。 说话风格建模对于表现力语音合成具有重要作用。 现有基于参考音频提取风格表征的方法通常利用文本的语义相似度进行参考音频选择&#xff0c;忽略了语义信息和说话风格的差异性。 本文…

大厂都在用MyBatis,跳槽的时候MyBatis更是面试必问的内容,那你对于MyBatis又掌握了多少呢?这份MyBatis源码解析值得拥有!

MyBatis作为一个流行的半自动ORM框架&#xff0c;里面融合了许多优秀的设计理念&#xff0c;分析其源码骨架能够帮你建立良好的项目设计经验。由于其比较复杂&#xff0c;我会分成几篇来讲&#xff0c;一起踏上征服的旅程吧&#xff01; 首先把MyBatis源码包导入到idea&#x…

python+django汽车租赁系统pycharm项目

目录 1 绪论 1 1.1课题背景 1 1.2课题研究现状 1 1.3初步设计方法与实施方案 2 1.4本文研究内容 2 4 2.3 B/S结构简介 4 2.4MySQL数据库 5 3 系统分析 6 3.1系统可行性分析 6 3.1.1经济可行性 6 3.1.2技术可行性 6 3.1.3运行可行性 6 3.2系统现状分析 6 3.3功能需求分析 7 …

Apollo 应用与源码分析:Monitor监控-软件监控-时间延迟监控

目录 代码 分析 RunOnce 函数分析 UpdateState函数分析 发送时间延迟报告函数分析 备注 代码 class LatencyMonitor : public RecurrentRunner {public:LatencyMonitor();void RunOnce(const double current_time) override;bool GetFrequency(const std::string& ch…

Git---idea中git的基本操作

idea中使用git仓库 idea中配置git仓库&#xff1a; 首先idea配置git仓库的位置 配置完成之后&#xff0c;有两种创建仓库的方式 从本地配置git仓库&#xff1a; idea本身设置好的&#xff0c;直接下一步就好 从远程克隆仓库&#xff1a; 如果远程仓库没有的话可以绑定完…

CDMP考试时间与报名方式

CDMP“数据管理专业人士认证”证书国际通用&#xff0c;行业认可度极高&#xff0c;是一项涵盖学历教育、工作经验和专业知识考试在内的综合资格认证&#xff0c;也是 目前全球唯一数据管理方面权威性认证 。CDMP考试时间是什么时候&#xff1f;怎样报名&#xff1f;今天小编来…

从ChargePoint到能链智电,充电服务商的价值创新

近日&#xff0c;吉林长春出租车雨雪之中排队换电艰难的视频引起热议。 新能源汽车充换电困难&#xff0c;一方面说明电池在寒冷天气下的性能有优化空间&#xff0c;另一方面也反映出国内新能源汽车配套基础设施仍然存在较大需求缺口。 充电基础设施建设对新能源汽车推广意义…

使用Spark的foreach算子及UDTF函数实现MySQL数据的一对多【Java】

使用Spark的foreach算子及UDTF函数实现MySQL数据的一对多【Java】 背景 我们的数仓项目中遇到了这样一种场景&#xff0c;脱敏后内容大致如下&#xff1a; col1col2time1time2a1b12022-01-01 00:00:002022-01-05 00:00:00a2b22022-01-28 00:00:002022-02-03 00:00:00a3b3202…