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

【做一道算一道】和为 K 的子数组

给你一个整数数组 nums 和一个整数 k ,请你统计并返回 该数组中和为 k 的子数组的个数 。

子数组是数组中元素的连续非空序列。

示例 1:

输入:nums = [1,1,1], k = 2
输出:2
示例 2:

输入:nums = [1,2,3], k = 3
输出:2

提示:

1 <= nums.length <= 2 * 104
-1000 <= nums[i] <= 1000
-107 <= k <= 107

思路

看到想到是滑动窗口,调了力扣结果和本地调的对不上,看题解,发现说有负值,那滑动就不行。
官解是前缀和,记一下。
其中关键代码是:

count += mp[pre - k]; // 如果存在前缀和为pre - k,更新count

表示如果mp中存在pre - k,说明存在一个前缀和为pre - k,那么从这个前缀和的末尾到当前索引的子数组和为k。即从pre - k前缀和的末尾到当前索引位置的子数组满足条件,可被记录。
因此,将count增加mp[pre - k](该前缀和出现的次数,每个对应一种满足的情况)。
在这里插入图片描述

代码

滑动窗口(仅适合全为正):
奇怪的点,全为正的时候,本地调是正确的,力扣上结果就不对,不知道哪儿有问题。

class Solution {
public:int subarraySum(vector<int>& nums, int k) {int sum=0;int l=0,r=0;int cnt=0;sort(nums.begin(),nums.end());if(k<nums[0])return cnt;while(r<nums.size()){sum+=nums[r++];while(sum>=k){if(sum==k){cnt++;}sum-=nums[l++];  }}return cnt;}
};

前缀和:

class Solution {
public:int subarraySum(vector<int>& nums, int k) {unordered_map<int, int> mp;mp[0] = 1; // 初始化前缀和为0的出现次数为1int count = 0, pre = 0;for (auto x : nums) {pre += x; // 更新前缀和count += mp[pre - k]; // 如果存在前缀和为pre - k,更新countmp[pre]++; // 更新当前前缀和的出现次数}return count;}
};

官解当中多一个判定:

if (mp.find(pre - k) != mp.end())

可省略,因为即使 mp[pre - k] 之前没有出现过,其值也是0,不会对 count 产生影响。

相关文章:

【做一道算一道】和为 K 的子数组

给你一个整数数组 nums 和一个整数 k &#xff0c;请你统计并返回 该数组中和为 k 的子数组的个数 。 子数组是数组中元素的连续非空序列。 示例 1&#xff1a; 输入&#xff1a;nums [1,1,1], k 2 输出&#xff1a;2 示例 2&#xff1a; 输入&#xff1a;nums [1,2,3],…...

Facebook应用开发:认证与授权登录流程详解

Facebook作为全球最大的社交平台之一&#xff0c;提供了强大的认证与授权机制&#xff0c;允许第三方应用通过Facebook登录来简化用户的注册和登录流程。本文将详细介绍Facebook应用开发中的认证和授权登录流程&#xff0c;以及如何在应用中实现这一功能。 关键词 Facebook登…...

实战:搭建一款属于自己的个人知识库~docusaurus(强大且丝滑)-2024.7.7(测试成功)

目录 文章目录 目录docusaurus简介效果专题链接&#x1f44f;环境源码1、安装基础环境2、拉取代码3、安装坚果云并同步md核心文件4、构建运行5、配置脚本环境1.配置vscode终端到ecs的免密2.配置win10 vscode终端环境变量 6、构建并推送静态文件到ecs关于我最后最后 docusaurus简…...

Java教程之IO模式精讲,NIO+BIO

第一章 BIO、NIO、AIO介绍 背景 在java的软件设计开发中&#xff0c;通信架构是不可避免的&#xff0c;我们在进行不同系统或者不同进程之间的数据交互&#xff0c;或 者在高并发下的通信场景下都需要用到网络通信相关的技术&#xff0c;对于一些经验丰富的程序员来说&#x…...

如何让代码兼容 Python 2 和 Python 3?Future 库助你一臂之力

目录 01Future 是什么? 为什么选择 Future? 安装与配置 02Future 的基本用法 1、兼容 print 函数 2、兼容整数除法 3、兼容 Unicode 字符串 03Future 的高级功能 1. 处理字符串与字节 2. 统一异常处理…...

AI让大龄程序员重新焕发活力

AI是在帮助开发者还是取代他们&#xff1f; 在软件开发领域&#xff0c;生成式人工智能&#xff08;AIGC&#xff09;正在改变开发者的工作方式。无论是代码生成、错误检测还是自动化测试&#xff0c;AI工具正在成为开发者的得力助手。然而&#xff0c;这也引发了对开发者职业…...

Python在现代办公自动化中的应用:会不会被裁?就看你的效率了!

Python在现代办公自动化中的应用&#xff1a;提升效率的艺术 Python&#xff0c;作为一门简洁而强大的编程语言&#xff0c;已经成为许多办公室英雄优化日常工作的秘密武器。本文将带你探索Python如何在办公自动化领域大放异彩&#xff0c;并且会巧妙融入开源神器PlugLink&…...

Laravel5+mycat 报错 “Packets out of order”

背景 近期对负责项目&#xff0c;配置了一套 主从复制的 MySQL 集群 使用了中间件 mycat 但测试发现&#xff0c;替换了原来的数据连接后&#xff0c;会出现 Packets out of order 的报错 同时注意到&#xff0c;有的框架代码中竟然也会失效&#xff0c;比如 controller 类中&…...

使用androidx.appcompat:appcompat:1.7.0无法运行的问题

问题&#xff1a; 使用 implementation ‘androidx.appcompat:appcompat:1.7.0’ 出现无法运行的问题&#xff0c;编译都没有问题 AGPBI: {“kind”:“error”,“text”:“java.lang.NullPointerException”,“sources”:[{“file”:“C:\Users\10557\.gradle\caches\transfor…...

基于Java的水果商品销售网站

1 水果商品销售网站概述 1.1 课题简介 随着电子商务在当今社会的迅猛发展&#xff0c;水果在线销售已逐渐演变为一种极为便捷的购物方式&#xff0c;日益受到人们的青睐。本系统的设计初衷便是构建一个功能完备、用户体验友好的水果销售平台&#xff0c;致力于为用户提供优质、…...

Redis 线程模型

0、参考 【Redis线程模型】 【big key 排查和解决思路】 1、 Redis 单线程的理解 为什么单线程&#xff1a;CPU不是性能瓶颈&#xff08;内存和网络&#xff09;&#xff0c;单线程能够达到业务要求 网络IO和键值对读写都是由一个线程完成的 2、 Redis 多线程的理解 持久化…...

栈和队列---循环队列

1.循环队列的出现 &#xff08;1&#xff09;上面的这个就是一个普通的数据的入队和出队的过程我们正常情况下去实现这个入队和出队的过程&#xff0c;就是这个数据从这个队尾进入&#xff0c;从队头离开&#xff0c;但是这个加入的时候肯定是没有其他的问题的&#xff0c;直接…...

打卡第4天----链表

通过学习基础&#xff0c;发现我的基本功还得需要再练练&#xff0c;思路得再更加清晰明了&#xff0c;这样子做算法题才能驾轻就熟。每天记录自己的进步。 一、两两交换 题目编号&#xff1a;24 题目描述&#xff1a; 给你一个链表&#xff0c;两两交换其中相邻的节点&#x…...

07-7.1.1 查找的基本概念

&#x1f44b; Hi, I’m Beast Cheng &#x1f440; I’m interested in photography, hiking, landscape… &#x1f331; I’m currently learning python, javascript, kotlin… &#x1f4eb; How to reach me --> 458290771qq.com 喜欢《数据结构》部分笔记的小伙伴可以…...

【数据结构与算法】快速排序双指针法

&#x1f493; 博客主页&#xff1a;倔强的石头的CSDN主页 &#x1f4dd;Gitee主页&#xff1a;倔强的石头的gitee主页 ⏩ 文章专栏&#xff1a;《数据结构与算法》 期待您的关注 ​...

GESP C++一级真题

PDF图片1-7 点赞❤️关注&#x1f60d;收藏⭐️ 互粉必回&#x1f64f;&#x1f64f;&#x1f64f;...

短信验证码实现

一、设置AccessKey 创建用户并配置使用权限&#xff0c;使我们拥有调用 aliyunAPI 的权限&#xff0c;之后会生成 AccessKeyID 和 AccessKey密码&#xff0c;后面我们会使用到。需要注意的是 AccessKeyID 和 AccessKey密码生成后我们需要将他保存起来&#xff0c;否则后期无法查…...

pnpm的坑

请问pnpm的两个坑怎么解决&#xff1a; 第一个坑&#xff1a;没有节省磁盘空间 我已经配置了依赖的存储位置&#xff0c; 但我在项目里pnpm install以后&#xff0c;发现依赖包还是很大&#xff0c; 然后发现里面的链接并不是指向先前配置的依赖存储位置&#xff0c;而是指…...

如何监控和分析 PostgreSQL 中的查询执行计划?

文章目录 一、为什么监控和分析查询执行计划很重要二、PostgreSQL 中用于获取查询执行计划的方法三、理解查询执行计划的关键元素四、通过示例分析查询执行计划五、优化查询执行计划的常见策略六、使用工具辅助分析七、结合实际案例的详细分析八、总结 在 PostgreSQL 数据库中&…...

ruoyi-cloud登录接口实现滑块验证码

一、前言 ruoyi项目默认的验证码是这样的 今天来尝试增加滑块验证码&#xff0c;我们用到的是tianai-captcha。 文档地址&#xff1a;http://doc.captcha.tianai.cloud/ 源码地址&#xff1a;https://gitee.com/tianai/tianai-captcha 下面来看具体的步骤。 二、后端 在g…...

RocketMQ延迟消息机制

两种延迟消息 RocketMQ中提供了两种延迟消息机制 指定固定的延迟级别 通过在Message中设定一个MessageDelayLevel参数&#xff0c;对应18个预设的延迟级别指定时间点的延迟级别 通过在Message中设定一个DeliverTimeMS指定一个Long类型表示的具体时间点。到了时间点后&#xf…...

系统设计 --- MongoDB亿级数据查询优化策略

系统设计 --- MongoDB亿级数据查询分表策略 背景Solution --- 分表 背景 使用audit log实现Audi Trail功能 Audit Trail范围: 六个月数据量: 每秒5-7条audi log&#xff0c;共计7千万 – 1亿条数据需要实现全文检索按照时间倒序因为license问题&#xff0c;不能使用ELK只能使用…...

精益数据分析(97/126):邮件营销与用户参与度的关键指标优化指南

精益数据分析&#xff08;97/126&#xff09;&#xff1a;邮件营销与用户参与度的关键指标优化指南 在数字化营销时代&#xff0c;邮件列表效度、用户参与度和网站性能等指标往往决定着创业公司的增长成败。今天&#xff0c;我们将深入解析邮件打开率、网站可用性、页面参与时…...

【C++进阶篇】智能指针

C内存管理终极指南&#xff1a;智能指针从入门到源码剖析 一. 智能指针1.1 auto_ptr1.2 unique_ptr1.3 shared_ptr1.4 make_shared 二. 原理三. shared_ptr循环引用问题三. 线程安全问题四. 内存泄漏4.1 什么是内存泄漏4.2 危害4.3 避免内存泄漏 五. 最后 一. 智能指针 智能指…...

打手机检测算法AI智能分析网关V4守护公共/工业/医疗等多场景安全应用

一、方案背景​ 在现代生产与生活场景中&#xff0c;如工厂高危作业区、医院手术室、公共场景等&#xff0c;人员违规打手机的行为潜藏着巨大风险。传统依靠人工巡查的监管方式&#xff0c;存在效率低、覆盖面不足、判断主观性强等问题&#xff0c;难以满足对人员打手机行为精…...

pycharm 设置环境出错

pycharm 设置环境出错 pycharm 新建项目&#xff0c;设置虚拟环境&#xff0c;出错 pycharm 出错 Cannot open Local Failed to start [powershell.exe, -NoExit, -ExecutionPolicy, Bypass, -File, C:\Program Files\JetBrains\PyCharm 2024.1.3\plugins\terminal\shell-int…...

小木的算法日记-多叉树的递归/层序遍历

&#x1f332; 从二叉树到森林&#xff1a;一文彻底搞懂多叉树遍历的艺术 &#x1f680; 引言 你好&#xff0c;未来的算法大神&#xff01; 在数据结构的世界里&#xff0c;“树”无疑是最核心、最迷人的概念之一。我们中的大多数人都是从 二叉树 开始入门的&#xff0c;它…...

C++_哈希表

本篇文章是对C学习的哈希表部分的学习分享 相信一定会对你有所帮助~ 那咱们废话不多说&#xff0c;直接开始吧&#xff01; 一、基础概念 1. 哈希核心思想&#xff1a; 哈希函数的作用&#xff1a;通过此函数建立一个Key与存储位置之间的映射关系。理想目标&#xff1a;实现…...

【实施指南】Android客户端HTTPS双向认证实施指南

&#x1f510; 一、所需准备材料 证书文件&#xff08;6类核心文件&#xff09; 类型 格式 作用 Android端要求 CA根证书 .crt/.pem 验证服务器/客户端证书合法性 需预置到Android信任库 服务器证书 .crt 服务器身份证明 客户端需持有以验证服务器 客户端证书 .crt 客户端身份…...

边缘计算网关提升水产养殖尾水处理的远程运维效率

一、项目背景 随着水产养殖行业的快速发展&#xff0c;养殖尾水的处理成为了一个亟待解决的环保问题。传统的尾水处理方式不仅效率低下&#xff0c;而且难以实现精准监控和管理。为了提升尾水处理的效果和效率&#xff0c;同时降低人力成本&#xff0c;某大型水产养殖企业决定…...