news 2026/8/21 3:21:33

力扣hot100菜鸟版 题号560

作者头像

张小明

前端开发工程师

1.2k 24
文章封面图
力扣hot100菜鸟版 题号560

题目

废话少说,直接看题目,首先理解一下题意,子数组的要求是数组中元素的连续非空序列。

在示例1中,就是下标0,1和下标1,2这两个子数组。

然后是示例2,下标0,1是显然的,我看了好久都没找到第二个在哪,问了ai才知道下标2就是一个子数组,不知道有没有和我一样的人(哭笑不得)

思路

帮大家试过二重循坏暴力解法了,过不去

熟悉的人肯定知道这题考察的是前缀和,但是别急,先让我们看看前缀和的基本原理。

对一个元素序列:3,4,56,6,7,6,7

当我们要求下标2到下标4闭区间的和时,我们应该怎么做?

注意到公式,下标0到下标4闭区间的和减去从下标0到下标1闭区间的和,即为所求。这就是前缀和的基本原理,线性遍历得到前缀和,通过不同下标的前缀和相减得到任意区间的和,符合空间换时间的思想。前缀和基本公式:

下标闭区间L,R的区间和=R的前缀和减去L-1的前缀和

(看了一些视频,感觉前缀和的理解有多种,有些前缀和好像是开区间的,整体思路是一样的,这里我采用闭区间的思路)

代码

class Solution { public: int subarraySum(vector<int>& nums, int k) { unordered_map <int,int> map;//key为前缀和,value为这个前缀和出现的次数 map[0]=1;//这个要特别注意,下文有解释 int pre_sum=0; int res=0; for(int i=0;i<nums.size();i++){ pre_sum+=nums[i]; if(map.find(pre_sum-k)!=map.end()) res+=map[pre_sum-k]; map[pre_sum]++; } return res; } };

(这个代码里面的注释咋改颜色啊,根本看不清啊)

考虑如下序列:1。给定的k也为1。

按照代码逻辑,此时寻找map中是否存在key,使其等于pre_sum-k即1-1即0,如果代码中没有设置

map[0]=1的话,就漏解了。接下来要思考为啥有这个特殊情况,难道上面的思路有问题?

根据公式,想要计算下标0到下标0的闭区间的和,需要用下标0的前缀和减去“下标-1”的前缀和,

所以咱们的思路没问题。

碎碎念

最近懈怠了十几天,罪过罪过,明天继续努力!

版权声明: 本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若内容造成侵权/违法违规/事实不符,请联系邮箱:809451989@qq.com进行投诉反馈,一经查实,立即删除!
网站建设 2026/8/20 6:21:48

基于PaddlePaddle镜像的OCR流水线设计:适用于票据识别场景

基于PaddlePaddle镜像的OCR流水线设计&#xff1a;适用于票据识别场景 在金融、税务和物流等行业加速数字化转型的今天&#xff0c;每天都有海量的发票、收据、订单等纸质或扫描票据需要录入系统。传统依赖人工录入的方式不仅效率低下——一张发票平均耗时3到5分钟&#xff0c;…

作者头像 李华
网站建设 2026/8/19 4:19:31

ESP32-CAM图像传输协议解析:MJPG与TCP的性能对比分析

ESP32-CAM图像传输实战&#xff1a;MJPG与原始帧TCP的性能实测与选型指南你有没有遇到过这样的情况&#xff1f;调试ESP32-CAM时&#xff0c;画面卡顿、延迟高得离谱&#xff0c;甚至几秒才刷新一帧。换了个客户端还是老样子&#xff0c;Wi-Fi信号也不差——问题到底出在哪&…

作者头像 李华
网站建设 2026/8/18 18:56:23

es教程新手友好:配置本地开发环境步骤详解

从零开始搭建 Elasticsearch 本地开发环境&#xff1a;新手也能轻松上手 你是不是也曾在项目中听到“我们用的是 ELK 做日志分析”&#xff1f;或者面试时被问到&#xff1a;“你会用 Elasticsearch 写查询吗&#xff1f;”——如果你点头说会&#xff0c;但心里却在嘀咕“Ela…

作者头像 李华
网站建设 2026/8/14 20:23:34

跨平台开发效率提升:交叉编译最佳实践总结

跨平台开发效率提升&#xff1a;交叉编译实战指南与工程避坑全解析 你有没有经历过这样的场景&#xff1f; 在一块ARM开发板上跑 make 编译一个中等规模的C项目&#xff0c;风扇狂转、进度条爬得比蜗牛还慢——三小时后终于链接成功&#xff0c;结果运行时报错“非法指令”。…

作者头像 李华
网站建设 2026/8/3 15:15:12

系统缺少找不到d3d10.dll文件 如何下载修复问题?

在使用电脑系统时经常会出现丢失找不到某些文件的情况&#xff0c;由于很多常用软件都是采用 Microsoft Visual Studio 编写的&#xff0c;所以这类软件的运行需要依赖微软Visual C运行库&#xff0c;比如像 QQ、迅雷、Adobe 软件等等&#xff0c;如果没有安装VC运行库或者安装…

作者头像 李华
网站建设 2026/8/19 22:43:47

PaddlePaddle镜像与Spark整合进行大规模特征工程尝试

PaddlePaddle镜像与Spark整合进行大规模特征工程尝试 在推荐系统、广告点击率预估和内容理解等工业级AI应用中&#xff0c;一个常被低估但至关重要的现实是&#xff1a;80%的时间花在数据准备上&#xff0c;而只有20%用于模型训练本身。当企业面对每天TB级的用户行为日志时&…

作者头像 李华