当前位置: 首页 > 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…...

XCTF-web-easyupload

试了试php&#xff0c;php7&#xff0c;pht&#xff0c;phtml等&#xff0c;都没有用 尝试.user.ini 抓包修改将.user.ini修改为jpg图片 在上传一个123.jpg 用蚁剑连接&#xff0c;得到flag...

ESP32读取DHT11温湿度数据

芯片&#xff1a;ESP32 环境&#xff1a;Arduino 一、安装DHT11传感器库 红框的库&#xff0c;别安装错了 二、代码 注意&#xff0c;DATA口要连接在D15上 #include "DHT.h" // 包含DHT库#define DHTPIN 15 // 定义DHT11数据引脚连接到ESP32的GPIO15 #define D…...

Linux云原生安全:零信任架构与机密计算

Linux云原生安全&#xff1a;零信任架构与机密计算 构建坚不可摧的云原生防御体系 引言&#xff1a;云原生安全的范式革命 随着云原生技术的普及&#xff0c;安全边界正在从传统的网络边界向工作负载内部转移。Gartner预测&#xff0c;到2025年&#xff0c;零信任架构将成为超…...

Python爬虫(一):爬虫伪装

一、网站防爬机制概述 在当今互联网环境中&#xff0c;具有一定规模或盈利性质的网站几乎都实施了各种防爬措施。这些措施主要分为两大类&#xff1a; 身份验证机制&#xff1a;直接将未经授权的爬虫阻挡在外反爬技术体系&#xff1a;通过各种技术手段增加爬虫获取数据的难度…...

如何理解 IP 数据报中的 TTL?

目录 前言理解 前言 面试灵魂一问&#xff1a;说说对 IP 数据报中 TTL 的理解&#xff1f;我们都知道&#xff0c;IP 数据报由首部和数据两部分组成&#xff0c;首部又分为两部分&#xff1a;固定部分和可变部分&#xff0c;共占 20 字节&#xff0c;而即将讨论的 TTL 就位于首…...

C# 求圆面积的程序(Program to find area of a circle)

给定半径r&#xff0c;求圆的面积。圆的面积应精确到小数点后5位。 例子&#xff1a; 输入&#xff1a;r 5 输出&#xff1a;78.53982 解释&#xff1a;由于面积 PI * r * r 3.14159265358979323846 * 5 * 5 78.53982&#xff0c;因为我们只保留小数点后 5 位数字。 输…...

Aspose.PDF 限制绕过方案:Java 字节码技术实战分享(仅供学习)

Aspose.PDF 限制绕过方案&#xff1a;Java 字节码技术实战分享&#xff08;仅供学习&#xff09; 一、Aspose.PDF 简介二、说明&#xff08;⚠️仅供学习与研究使用&#xff09;三、技术流程总览四、准备工作1. 下载 Jar 包2. Maven 项目依赖配置 五、字节码修改实现代码&#…...

Qemu arm操作系统开发环境

使用qemu虚拟arm硬件比较合适。 步骤如下&#xff1a; 安装qemu apt install qemu-system安装aarch64-none-elf-gcc 需要手动下载&#xff0c;下载地址&#xff1a;https://developer.arm.com/-/media/Files/downloads/gnu/13.2.rel1/binrel/arm-gnu-toolchain-13.2.rel1-x…...

Cilium动手实验室: 精通之旅---13.Cilium LoadBalancer IPAM and L2 Service Announcement

Cilium动手实验室: 精通之旅---13.Cilium LoadBalancer IPAM and L2 Service Announcement 1. LAB环境2. L2公告策略2.1 部署Death Star2.2 访问服务2.3 部署L2公告策略2.4 服务宣告 3. 可视化 ARP 流量3.1 部署新服务3.2 准备可视化3.3 再次请求 4. 自动IPAM4.1 IPAM Pool4.2 …...

WEB3全栈开发——面试专业技能点P7前端与链上集成

一、Next.js技术栈 ✅ 概念介绍 Next.js 是一个基于 React 的 服务端渲染&#xff08;SSR&#xff09;与静态网站生成&#xff08;SSG&#xff09; 框架&#xff0c;由 Vercel 开发。它简化了构建生产级 React 应用的过程&#xff0c;并内置了很多特性&#xff1a; ✅ 文件系…...