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

leetcode分类刷题:哈希表(Hash Table)(四、前缀和 处理连续子数组)

1、leetcode题目里对于元素加和的考察可谓是屡见不鲜,包括 简单的限定一个有效答案的两个或多个元素求和leetcode分类刷题:哈希表(Hash Table)(一、简单的两数之和)、在有序数组内对加和等于target的三元组、四元组等的求解leetcode分类刷题:基于数组的双指针(三、有序数组的元素求和)以及连续子数组加和leetcode分类刷题:滑动窗口(一、基本子数组类型)
2、本文总结的题型同样为对连续子数组加和进行考察,区别于leetcode分类刷题:滑动窗口(一、基本子数组类型)的是,数组元素为整数,不是正整数了,因此需要按照 前缀和(按照闭区间形式,当前索引位置的值也算进去好理解)+哈希表 的思路进行解决,最后会发现这种题型就是leetcode分类刷题:哈希表(Hash Table)(一、简单的两数之和)的扩展,在解题模板上会有点类似

724. 寻找数组的中心下标

1、该题为典型的使用前缀和算法解决的问题,只需要两次遍历即可:第一次遍历求数组的和;第二次遍历求数组的前缀和,并判断对应位置是否为 中心下标
2、和1991. 找到数组的中间位置是完全一样的题目

from typing import List
'''
724. 寻找数组的中心下标
题目描述:给你一个整数数组nums ,请计算数组的 中心下标 。
数组 中心下标 是数组的一个下标,其左侧所有元素相加的和等于右侧所有元素相加的和。
如果中心下标位于数组最左端,那么左侧数之和视为 0 ,因为在下标的左侧不存在元素。这一点对于中心下标位于数组最右端同样适用。
如果数组有多个中心下标,应该返回 最靠近左边 的那一个。如果数组不存在中心下标,返回 -1 。
示例 1:输入:nums = [1, 7, 3, 6, 5, 6]输出:3解释:中心下标是 3 。左侧数之和 sum = nums[0] + nums[1] + nums[2] = 1 + 7 + 3 = 11 ,右侧数之和 sum = nums[4] + nums[5] = 5 + 6 = 11 ,二者相等。
题眼:左侧右侧数组的和
思路1、三次遍历:第一次遍历建立从左到右的加和数组,第二次遍历建立从右到左的加和数组,第三次遍历对加和数组的对应位置判断相等情况
思路2、前缀和(按照闭区间形式,当前索引位置的值也算进去好理解):第一次遍历:求数组的和;第二次遍历:求数组的前缀和,并判断对应位置是否为 中心下标
'''class Solution:def pivotIndex(self, nums: List[int]) -> int:# 思路1、三次遍历# leftSum = [0] * len(nums)# s = 0# for i in range(len(nums)):#     s += nums[i]#     leftSum[i] = s# rightSum = [0] * len(nums)# s = 0# for i in range(len(nums) - 1, -1, -1):#     s += nums[i]#     rightSum[i] = s# for i in range(len(leftSum)):#     if leftSum[i] == rightSum[i]:#         return i# return -1# 思路2、前缀和# 第一次遍历:求数组的和total = 0for n in nums:total += n# 第二次遍历:求数组的前缀和,并判断对应位置是否为 中心下标prefixSum = 0for i in range(len(nums)):prefixSum += nums[i]if prefixSum * 2 - nums[i] == total:  # 这个条件的判断没有想到!!return ireturn -1if __name__ == "__main__":obj = Solution()while True:try:in_line = input().strip().split('=')nums = [int(n) for n in in_line[1].split('[')[1].split(']')[0].split(',')]print(obj.pivotIndex(nums))except EOFError:break

560. 和为 K 的子数组

1、通过题眼连续子数组来判断,该题很像是滑动窗口的解法,但数组元素为整数,不是正整数,不满足滑窗右边界增大元素之和递增、左指针增大元素之和递减
2、要用前缀和(按照闭区间形式,当前索引位置的值也算进去好理解)+哈希表的思路!
3、通过这道题也认识到,如果“1. 两数之和”不是限定了样例只存在一个答案,其哈希表更新的逻辑有缺陷

from typing import List
'''
560. 和为 K 的子数组
题目描述:给你一个整数数组 nums 和一个整数 k ,请你统计并返回 该数组中和为 k 的连续子数组的个数 。
示例 1:输入:nums = [1,1,1], k = 2输出:2
题眼:连续子数组,很像是滑动窗口的解法,但数组元素为整数,不是正整数,不满足滑窗右边界增大元素之和递增、左指针增大元素之和递减 了
思路:无法用滑动窗口了;要用前缀和(按照闭区间形式,当前索引位置的值也算进去好理解)+哈希表的思路!
“1. 两数之和”的扩展:通过这道题也认识到,如果“1. 两数之和”不是限定了样例只存在一个答案,其哈希表更新的逻辑有缺陷
'''class Solution:def subarraySum(self, nums: List[int], k: int) -> int:result = 0hashTable = {0: 1}  # 这里保证了对 包含起始元素的连续子数组 的判断prefixSum = 0for n in nums:  # 查找 以当前遍历元素n对应的索引位置为 右边界的连续子数组prefixSum += n   # 前缀和(按照闭区间形式,当前索引位置的值也算进去好理解)# 1、先找 以当前遍历元素n对应的索引位置 之前的前缀和是否存在满足条件的if prefixSum - k in hashTable:result += hashTable[prefixSum - k]# 2、再将当前遍历元素n对应的索引位置 的前缀和添加到hashDictif prefixSum not in hashTable:hashTable[prefixSum] = 1else:hashTable[prefixSum] += 1return resultif __name__ == "__main__":obj = Solution()while True:try:in_line = input().strip().split('=')nums = [int(n) for n in in_line[1].split('[')[1].split(']')[0].split(',')]k = int(in_line[2].strip())print(obj.subarraySum(nums, k))except EOFError:break

974. 和可被 K 整除的子数组

1、“560. 和为 K 的子数组”的衍生题,思路为完全一致的前缀和(按照闭区间形式,当前索引位置的值也算进去好理解)+哈希表
2、这道题比较难想的是使用 同余定理:两个除以k余数相等的数字,其差一定可以整除k,即 (preSumJ - preSumI)%K = 0 等价于 preSumJ%K == preSumI%K

from typing import List
'''
974. 和可被 K 整除的子数组
题目描述:给定一个整数数组 nums 和一个整数 k ,返回其中元素之和可被 k 整除的(连续、非空) 子数组 的数目。
子数组 是数组的 连续 部分。
示例 1:输入:nums = [4,5,0,-2,-3,1], k = 5  输出:7解释:有 7 个子数组满足其元素之和可被 k = 5 整除:  [4, 5, 0, -2, -3, 1], [5], [5, 0], [5, 0, -2, -3], [0], [0, -2, -3], [-2, -3]
题眼:连续子数组;“560. 和为 K 的子数组”的衍生题
思路:要用前缀和(按照闭区间形式,当前索引位置的值也算进去好理解)+哈希表的思路
同时,需要使用 同余定理 (preSumJ - preSumI)%K = 0 等价于 preSumJ%K == preSumI%K
'''class Solution:def subarraysDivByK(self, nums: List[int], k: int) -> int:# 需要用到 同余定理,两个除以k余数相等的数字,其差一定可以整除kresult = 0hashTable = {0: 1}  # 这里保证了对 包含起始元素的连续子数组 的判断prefixSum = 0for n in nums:  # 查找 以当前遍历元素n对应索引位置为边界的连续子数组prefixSum += n  # 前缀和(按照闭区间形式,当前索引位置的值也算进去好理解)if prefixSum % k in hashTable:result += hashTable[prefixSum % k]hashTable[prefixSum % k] += 1else:hashTable[prefixSum % k] = 1return resultif __name__ == "__main__":obj = Solution()while True:try:in_line = input().strip().split('=')nums = [int(n) for n in in_line[1].split('[')[1].split(']')[0].split(',')]k = int(in_line[2].strip())print(obj.subarraysDivByK(nums, k))except EOFError:break

相关文章:

leetcode分类刷题:哈希表(Hash Table)(四、前缀和 处理连续子数组)

1、leetcode题目里对于元素加和的考察可谓是屡见不鲜,包括 简单的限定一个有效答案的两个或多个元素求和leetcode分类刷题:哈希表(Hash Table)(一、简单的两数之和)、在有序数组内对加和等于target的三元组…...

如何处理生产环境中的数据倾斜问题?

分析&回答 1、flink数据倾斜的表现: 任务节点频繁出现反压,增加并行度也不能解决问题 部分节点出现OOM异常,是因为大量的数据集中在某个节点上,导致该节点内存被爆,任务失败重启 2、数据倾斜产生的原因&#x…...

【WSN无线传感器网络恶意节点】使用 MATLAB 进行无线传感器网络部署研究

💥💥💞💞欢迎来到本博客❤️❤️💥💥 🏆博主优势:🌞🌞🌞博客内容尽量做到思维缜密,逻辑清晰,为了方便读者。 ⛳️座右铭&a…...

C# 实现浏览器控件设置

using System; using System.Collections.Generic; using System.ComponentModel; using System.Data; using System.Drawing; using System...

1130 - Host ‘17216.18083‘ is not allowed to connect to this MySQL server

mysql5.7 设置root远程登录 1、登录数据库 mysql -u root -p 2、设置root 用户允许远程登录,"your password" 是自己设置的密码; GRANT ALL PRIVILEGES ON *.* TO root% IDENTIFIED BY your password WITH GRANT OPTION; 3、刷新权限 FLUSH PRIVILEG…...

使用Spring的getBeansOfType实现接口多实现类的动态调用

使用Spring的getBeansOfType实现接口多实现类的动态调用 package com.xxl.job.admin.core.alarm;import com.xxl.job.admin.core.model.XxlJobInfo; import com.xxl.job.admin.core.model.XxlJobLog; import org.slf4j.Logger; import org.slf4j.LoggerFactory; import org.sp…...

(笔记三)opencv图像基础操作

强调:本文只为学习记录做笔记 详细可参考opencv官网 :https://docs.opencv.org/4.1.1/d0/d86/tutorial_py_image_arithmetics.html (1)将cv2的BGR模式改为RGB模式 #!/usr/bin/env python # -*- coding:utf-8 -*- ""&q…...

PHP入门及环境搭建 - XAMPP

文章目录 PHP简介搭建PHP环境(XAMPP)下载XAMPP安装XAMPP第1步:双击setup_xampp.bat检测第2步:启动Apache和MySQL第3步:浏览器访问内置的启动页面readme文档 - 必读运行Hello World程序下载并安装Eclipse for PHP编写Hello World程序参考目标: 1、了解PHP语言 2、搭建PHP开…...

开学季ipad手写笔什么牌子好?第三方电容笔推荐

自从ipad之类的平板电脑上出现了电容笔,电容笔就成功的取代了我们的手指,大大加快了我们的写作速度。不过,由于苹果pencil自带的先进芯片,导致其售价一直很高,给很多人,特别是学生,造成了很大的…...

【力扣】62. 不同路径 <动态规划>

【力扣】62. 不同路径 一个机器人位于一个 m m m x n n n 网格的左上角 (起始点在下图中标记为 “Start” )。 机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角(在下图中标记为 “Finish” )。问总共有多少条…...

【Python小项目】Python的GUI库Tkinter实现随机点名工具或抽奖工具并封装成.exe可执行文件

文章目录 一、项目背景二、需求分析UI界面设计如下:具体需求如下:二、实现思路三、项目关键代码读取excel中的人员名单实现随机滚动抽取主函数中Tkinter的界面相关操作实现窗口相关背景图设置组件相关完整代码四、将程序封装成.exe可执行文件将代码转换成.py文件五、总结与拓…...

【MySql】mysql之基础语句

一、常用的数据类型 类型解释举例int整型用于定义整数类型的数据(1、2、3、4、5…)float单精度浮点(4字节32位)准确表示小数点后六位double双精度浮点(8字节64位)小数位更多,更精确char固定长度…...

使用API调用获取商品数据的完整方案

在电子商务应用程序中,商品详情接口是不可或缺的一部分。它用于从电商平台或自己的数据库中获取商品数据,并将其提供给应用程序的其他部分使用。本文将详细介绍如何设计一个完整的商品详情接口方案,其中包括使用API调用来获取商品数据的过程。…...

来看看入门级别的室内设计创意是怎么样构成的

在这个世界上,信息源源不断地输送给我们,数字通信成为常态,对话的艺术正在逐渐消失;衡量一个人社交成功与否的最佳标准变为点赞数、粉丝数和高参与率;Ai人工智能引发了更快节奏的工作流程,工作要求越来越高…...

Go 面向对象(匿名字段)

概述 严格意义上说,GO语言中没有类(class)的概念,但是我们可以将结构体比作为类,因为在结构体中可以添加属性(成员),方法(函数)。 面向对象编程的好处比较多,我们先来说一下“继承…...

生成式AI,赋能数字劳动力的关键工具

人们认为,生成式人工智能是一种可以让他们用自己的话来提问或生成副本和图像的工具。事实也是如此,人工智能在这两方面上都做的非常好,但让人意想不到的是,它还蕴含着改变我们个人和专业工作的巨大潜力,能帮我们访问、…...

python提取邮件的附件,以excel为例

配置邮箱、读取基本的邮件内容请参考:python读取并解析邮箱邮件,读取邮件主题、内容、时间 以excel为例: 获取邮件: email_value_config {imap_server: imap.exmail.qq.com, username: xxxxxxxx.com, password: xxxxx, }# 连接…...

ZooKeeper技术内幕

文章目录 1、系统模型1.1、数据模型1.2、节点特性1.2.1、节点类型 1.3、版本——保证分布式数据原子性操作1.4、 Watcher——数据变更的通知1.5、ACL——保障数据的安全1.5.1、权限模式:Scheme1.5.2、授权对象:ID1.5.3、权限扩展体系 2、序列化与协议2.1…...

乱糟糟的YOLOv8-detect和pose训练自己的数据集

时代在进步,yolo在进步,我还在踏步,v8我浅搞了一下detect和pose,记录一下,我还是要吐槽一下,为啥子这个模型就放在了这个文件深处,如图。 以下教程只应用于直接应用yolov8,不修改。…...

【Nginx】Nginx $remote_addr和$proxy_add_x_forwarded_for变量详解

$remote_addr 代表客户端IP。注意,这里的客户端指的是直接请求Nginx的客户端,非间接请求的客户端。假设用户请求过程如下: 用户客户端--发送请求->Nginx1 --转发请求-->Nginx2->后端服务器那么,默认情况下,…...

iOS 26 携众系统重磅更新,但“苹果智能”仍与国行无缘

美国西海岸的夏天,再次被苹果点燃。一年一度的全球开发者大会 WWDC25 如期而至,这不仅是开发者的盛宴,更是全球数亿苹果用户翘首以盼的科技春晚。今年,苹果依旧为我们带来了全家桶式的系统更新,包括 iOS 26、iPadOS 26…...

阿里云ACP云计算备考笔记 (5)——弹性伸缩

目录 第一章 概述 第二章 弹性伸缩简介 1、弹性伸缩 2、垂直伸缩 3、优势 4、应用场景 ① 无规律的业务量波动 ② 有规律的业务量波动 ③ 无明显业务量波动 ④ 混合型业务 ⑤ 消息通知 ⑥ 生命周期挂钩 ⑦ 自定义方式 ⑧ 滚的升级 5、使用限制 第三章 主要定义 …...

PPT|230页| 制造集团企业供应链端到端的数字化解决方案:从需求到结算的全链路业务闭环构建

制造业采购供应链管理是企业运营的核心环节,供应链协同管理在供应链上下游企业之间建立紧密的合作关系,通过信息共享、资源整合、业务协同等方式,实现供应链的全面管理和优化,提高供应链的效率和透明度,降低供应链的成…...

Cinnamon修改面板小工具图标

Cinnamon开始菜单-CSDN博客 设置模块都是做好的,比GNOME简单得多! 在 applet.js 里增加 const Settings imports.ui.settings;this.settings new Settings.AppletSettings(this, HTYMenusonichy, instance_id); this.settings.bind(menu-icon, menu…...

Rust 异步编程

Rust 异步编程 引言 Rust 是一种系统编程语言,以其高性能、安全性以及零成本抽象而著称。在多核处理器成为主流的今天,异步编程成为了一种提高应用性能、优化资源利用的有效手段。本文将深入探讨 Rust 异步编程的核心概念、常用库以及最佳实践。 异步编程基础 什么是异步…...

【Java_EE】Spring MVC

目录 Spring Web MVC ​编辑注解 RestController RequestMapping RequestParam RequestParam RequestBody PathVariable RequestPart 参数传递 注意事项 ​编辑参数重命名 RequestParam ​编辑​编辑传递集合 RequestParam 传递JSON数据 ​编辑RequestBody ​…...

Redis的发布订阅模式与专业的 MQ(如 Kafka, RabbitMQ)相比,优缺点是什么?适用于哪些场景?

Redis 的发布订阅(Pub/Sub)模式与专业的 MQ(Message Queue)如 Kafka、RabbitMQ 进行比较,核心的权衡点在于:简单与速度 vs. 可靠与功能。 下面我们详细展开对比。 Redis Pub/Sub 的核心特点 它是一个发后…...

SiFli 52把Imagie图片,Font字体资源放在指定位置,编译成指定img.bin和font.bin的问题

分区配置 (ptab.json) img 属性介绍: img 属性指定分区存放的 image 名称,指定的 image 名称必须是当前工程生成的 binary 。 如果 binary 有多个文件,则以 proj_name:binary_name 格式指定文件名, proj_name 为工程 名&…...

处理vxe-table 表尾数据是单独一个接口,表格tableData数据更新后,需要点击两下,表尾才是正确的

修改bug思路: 分别把 tabledata 和 表尾相关数据 console.log() 发现 更新数据先后顺序不对 settimeout延迟查询表格接口 ——测试可行 升级↑:async await 等接口返回后再开始下一个接口查询 ________________________________________________________…...

【JVM面试篇】高频八股汇总——类加载和类加载器

目录 1. 讲一下类加载过程? 2. Java创建对象的过程? 3. 对象的生命周期? 4. 类加载器有哪些? 5. 双亲委派模型的作用(好处)? 6. 讲一下类的加载和双亲委派原则? 7. 双亲委派模…...