【做一道算一道】和为 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 ,请你统计并返回 该数组中和为 k 的子数组的个数 。 子数组是数组中元素的连续非空序列。 示例 1: 输入:nums [1,1,1], k 2 输出:2 示例 2: 输入:nums [1,2,3],…...
Facebook应用开发:认证与授权登录流程详解
Facebook作为全球最大的社交平台之一,提供了强大的认证与授权机制,允许第三方应用通过Facebook登录来简化用户的注册和登录流程。本文将详细介绍Facebook应用开发中的认证和授权登录流程,以及如何在应用中实现这一功能。 关键词 Facebook登…...
实战:搭建一款属于自己的个人知识库~docusaurus(强大且丝滑)-2024.7.7(测试成功)
目录 文章目录 目录docusaurus简介效果专题链接👏环境源码1、安装基础环境2、拉取代码3、安装坚果云并同步md核心文件4、构建运行5、配置脚本环境1.配置vscode终端到ecs的免密2.配置win10 vscode终端环境变量 6、构建并推送静态文件到ecs关于我最后最后 docusaurus简…...
Java教程之IO模式精讲,NIO+BIO
第一章 BIO、NIO、AIO介绍 背景 在java的软件设计开发中,通信架构是不可避免的,我们在进行不同系统或者不同进程之间的数据交互,或 者在高并发下的通信场景下都需要用到网络通信相关的技术,对于一些经验丰富的程序员来说&#x…...
如何让代码兼容 Python 2 和 Python 3?Future 库助你一臂之力
目录 01Future 是什么? 为什么选择 Future? 安装与配置 02Future 的基本用法 1、兼容 print 函数 2、兼容整数除法 3、兼容 Unicode 字符串 03Future 的高级功能 1. 处理字符串与字节 2. 统一异常处理…...
AI让大龄程序员重新焕发活力
AI是在帮助开发者还是取代他们? 在软件开发领域,生成式人工智能(AIGC)正在改变开发者的工作方式。无论是代码生成、错误检测还是自动化测试,AI工具正在成为开发者的得力助手。然而,这也引发了对开发者职业…...
Python在现代办公自动化中的应用:会不会被裁?就看你的效率了!
Python在现代办公自动化中的应用:提升效率的艺术 Python,作为一门简洁而强大的编程语言,已经成为许多办公室英雄优化日常工作的秘密武器。本文将带你探索Python如何在办公自动化领域大放异彩,并且会巧妙融入开源神器PlugLink&…...
Laravel5+mycat 报错 “Packets out of order”
背景 近期对负责项目,配置了一套 主从复制的 MySQL 集群 使用了中间件 mycat 但测试发现,替换了原来的数据连接后,会出现 Packets out of order 的报错 同时注意到,有的框架代码中竟然也会失效,比如 controller 类中&…...
使用androidx.appcompat:appcompat:1.7.0无法运行的问题
问题: 使用 implementation ‘androidx.appcompat:appcompat:1.7.0’ 出现无法运行的问题,编译都没有问题 AGPBI: {“kind”:“error”,“text”:“java.lang.NullPointerException”,“sources”:[{“file”:“C:\Users\10557\.gradle\caches\transfor…...
基于Java的水果商品销售网站
1 水果商品销售网站概述 1.1 课题简介 随着电子商务在当今社会的迅猛发展,水果在线销售已逐渐演变为一种极为便捷的购物方式,日益受到人们的青睐。本系统的设计初衷便是构建一个功能完备、用户体验友好的水果销售平台,致力于为用户提供优质、…...
Redis 线程模型
0、参考 【Redis线程模型】 【big key 排查和解决思路】 1、 Redis 单线程的理解 为什么单线程:CPU不是性能瓶颈(内存和网络),单线程能够达到业务要求 网络IO和键值对读写都是由一个线程完成的 2、 Redis 多线程的理解 持久化…...
栈和队列---循环队列
1.循环队列的出现 (1)上面的这个就是一个普通的数据的入队和出队的过程我们正常情况下去实现这个入队和出队的过程,就是这个数据从这个队尾进入,从队头离开,但是这个加入的时候肯定是没有其他的问题的,直接…...
打卡第4天----链表
通过学习基础,发现我的基本功还得需要再练练,思路得再更加清晰明了,这样子做算法题才能驾轻就熟。每天记录自己的进步。 一、两两交换 题目编号:24 题目描述: 给你一个链表,两两交换其中相邻的节点&#x…...
07-7.1.1 查找的基本概念
👋 Hi, I’m Beast Cheng 👀 I’m interested in photography, hiking, landscape… 🌱 I’m currently learning python, javascript, kotlin… 📫 How to reach me --> 458290771qq.com 喜欢《数据结构》部分笔记的小伙伴可以…...
【数据结构与算法】快速排序双指针法
💓 博客主页:倔强的石头的CSDN主页 📝Gitee主页:倔强的石头的gitee主页 ⏩ 文章专栏:《数据结构与算法》 期待您的关注 ...
GESP C++一级真题
PDF图片1-7 点赞❤️关注😍收藏⭐️ 互粉必回🙏🙏🙏...
短信验证码实现
一、设置AccessKey 创建用户并配置使用权限,使我们拥有调用 aliyunAPI 的权限,之后会生成 AccessKeyID 和 AccessKey密码,后面我们会使用到。需要注意的是 AccessKeyID 和 AccessKey密码生成后我们需要将他保存起来,否则后期无法查…...
pnpm的坑
请问pnpm的两个坑怎么解决: 第一个坑:没有节省磁盘空间 我已经配置了依赖的存储位置, 但我在项目里pnpm install以后,发现依赖包还是很大, 然后发现里面的链接并不是指向先前配置的依赖存储位置,而是指…...
如何监控和分析 PostgreSQL 中的查询执行计划?
文章目录 一、为什么监控和分析查询执行计划很重要二、PostgreSQL 中用于获取查询执行计划的方法三、理解查询执行计划的关键元素四、通过示例分析查询执行计划五、优化查询执行计划的常见策略六、使用工具辅助分析七、结合实际案例的详细分析八、总结 在 PostgreSQL 数据库中&…...
ruoyi-cloud登录接口实现滑块验证码
一、前言 ruoyi项目默认的验证码是这样的 今天来尝试增加滑块验证码,我们用到的是tianai-captcha。 文档地址:http://doc.captcha.tianai.cloud/ 源码地址:https://gitee.com/tianai/tianai-captcha 下面来看具体的步骤。 二、后端 在g…...
基于大模型的 UI 自动化系统
基于大模型的 UI 自动化系统 下面是一个完整的 Python 系统,利用大模型实现智能 UI 自动化,结合计算机视觉和自然语言处理技术,实现"看屏操作"的能力。 系统架构设计 #mermaid-svg-2gn2GRvh5WCP2ktF {font-family:"trebuchet ms",verdana,arial,sans-…...
CTF show Web 红包题第六弹
提示 1.不是SQL注入 2.需要找关键源码 思路 进入页面发现是一个登录框,很难让人不联想到SQL注入,但提示都说了不是SQL注入,所以就不往这方面想了 先查看一下网页源码,发现一段JavaScript代码,有一个关键类ctfs…...
简易版抽奖活动的设计技术方案
1.前言 本技术方案旨在设计一套完整且可靠的抽奖活动逻辑,确保抽奖活动能够公平、公正、公开地进行,同时满足高并发访问、数据安全存储与高效处理等需求,为用户提供流畅的抽奖体验,助力业务顺利开展。本方案将涵盖抽奖活动的整体架构设计、核心流程逻辑、关键功能实现以及…...
uniapp微信小程序视频实时流+pc端预览方案
方案类型技术实现是否免费优点缺点适用场景延迟范围开发复杂度WebSocket图片帧定时拍照Base64传输✅ 完全免费无需服务器 纯前端实现高延迟高流量 帧率极低个人demo测试 超低频监控500ms-2s⭐⭐RTMP推流TRTC/即构SDK推流❌ 付费方案 (部分有免费额度&#x…...
相机Camera日志分析之三十一:高通Camx HAL十种流程基础分析关键字汇总(后续持续更新中)
【关注我,后续持续新增专题博文,谢谢!!!】 上一篇我们讲了:有对最普通的场景进行各个日志注释讲解,但相机场景太多,日志差异也巨大。后面将展示各种场景下的日志。 通过notepad++打开场景下的日志,通过下列分类关键字搜索,即可清晰的分析不同场景的相机运行流程差异…...
VM虚拟机网络配置(ubuntu24桥接模式):配置静态IP
编辑-虚拟网络编辑器-更改设置 选择桥接模式,然后找到相应的网卡(可以查看自己本机的网络连接) windows连接的网络点击查看属性 编辑虚拟机设置更改网络配置,选择刚才配置的桥接模式 静态ip设置: 我用的ubuntu24桌…...
虚拟电厂发展三大趋势:市场化、技术主导、车网互联
市场化:从政策驱动到多元盈利 政策全面赋能 2025年4月,国家发改委、能源局发布《关于加快推进虚拟电厂发展的指导意见》,首次明确虚拟电厂为“独立市场主体”,提出硬性目标:2027年全国调节能力≥2000万千瓦࿰…...
c# 局部函数 定义、功能与示例
C# 局部函数:定义、功能与示例 1. 定义与功能 局部函数(Local Function)是嵌套在另一个方法内部的私有方法,仅在包含它的方法内可见。 • 作用:封装仅用于当前方法的逻辑,避免污染类作用域,提升…...
Unity中的transform.up
2025年6月8日,周日下午 在Unity中,transform.up是Transform组件的一个属性,表示游戏对象在世界空间中的“上”方向(Y轴正方向),且会随对象旋转动态变化。以下是关键点解析: 基本定义 transfor…...
企业大模型服务合规指南:深度解析备案与登记制度
伴随AI技术的爆炸式发展,尤其是大模型(LLM)在各行各业的深度应用和整合,企业利用AI技术提升效率、创新服务的步伐不断加快。无论是像DeepSeek这样的前沿技术提供者,还是积极拥抱AI转型的传统企业,在面向公众…...
