【做一道算一道】和为 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 产生影响。

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/371422.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

(详细版)学生管理系统(姓名、成绩、学号)---顺序表

//1:创建顺序表 //2:判满 //3:判空 //4:插入学生信息 //5:输出学生信息 //6:按位置插入学生信息 //7:按位置删除学生信息 //8:按位置修改学生信息 //9:按学号查找学生信息 //10:顺序表去重 //11:销毁顺序表 main.c&#xff1a; int main(int argc, const char *argv[]) {seq_p…

Maven一键配置阿里云远程仓库,让你的项目依赖飞起来!

文章目录 引言一、为什么选择阿里云Maven仓库&#xff1f;二、如何设置Maven阿里云远程仓库&#xff1f;三、使用阿里云Maven仓库的注意事项总结 引言 在软件开发的世界里&#xff0c;Maven无疑是一个强大的项目管理工具&#xff0c;它能够帮助我们自动化构建、依赖管理和项目…

Flutter集成高德导航SDK(Android篇)(JAVA语法)

先上flutter doctor&#xff1a; flutter sdk版本为&#xff1a;3.19.4 引入依赖&#xff1a; 在app的build.gradle下&#xff0c;添加如下依赖&#xff1a; implementation com.amap.api:navi-3dmap:10.0.700_3dmap10.0.700navi-3dmap里面包含了定位功能&#xff0c;地图功能…

计数排序的实现

原理 对一个数组进行遍历&#xff0c;再创建一个count数组 每找到一个值则在count数组中对应的位置加一&#xff0c;再在count数组中找到数字上方的count值&#xff0c;count值为几&#xff0c;则打印几次数组中的值. 开空间 相对映射 排序的实现 void CountSort(int* a, i…

鸿蒙开发:Universal Keystore Kit(密钥管理服务)【明文导入密钥(C/C++)】

明文导入密钥(C/C) 以明文导入ECC密钥为例。具体的场景介绍及支持的算法规格 在CMake脚本中链接相关动态库 target_link_libraries(entry PUBLIC libhuks_ndk.z.so)开发步骤 指定密钥别名keyAlias。 密钥别名的最大长度为64字节。 封装密钥属性集和密钥材料。通过[OH_Huks_I…

读人工智能全传05专家系统

1. 知识就是力量 1.1. 人工智能领域此前存在的问题是过度关注搜索和解决问题这种通用法则 1.2. “弱”方法缺少一个关键的要素&#xff0c;而这一要素才是在所有智能行为中起决定性作用的组成部分&#xff1a;知识 1.3. 一种基于知识的人工智能系统&#xff1a;专家系统开始…

weblogic加入第三方数据库代理驱动jar包(Oracle为例)

做的是国企项目&#xff0c;项目本身业务并不复杂&#xff0c;最复杂的却是服务器部署问题&#xff0c;对方给提供的服务器分内网、外网交换网&#xff0c;应用在交换网&#xff0c;数据库在内网&#xff0c;应用不能直接访问内网数据库&#xff0c;只能通过安全隔离网闸访问内…

Python爬虫与数据可视化:构建完整的数据采集与分析流程

Python爬虫技术概述 Python爬虫是一种自动化的数据采集工具&#xff0c;它可以模拟浏览器行为&#xff0c;访问网页并提取所需信息。Python爬虫的实现通常涉及以下几个步骤&#xff1a; 发送网页请求&#xff1a;使用requests库向目标网站发送HTTP请求。获取网页内容&#xf…

进入防火墙Web管理页面(eNSP USG6000V)和管理员模块

1、进入防火墙Web管理页面 USG系列是华为提供的一款高端防火墙产品&#xff0c;其特点在于提供强大的安全防护能力和灵活的扩展性。 以eNSP中的USG6000为例&#xff1a; MGMT口&#xff08;web管理口&#xff09;&#xff1a;对应设备上的G0/0/0口&#xff0c;上面初始配有一…

张量分解(2)——张量运算(内积、外积、直积、范数)

&#x1f345; 写在前面 &#x1f468;‍&#x1f393; 博主介绍&#xff1a;大家好&#xff0c;这里是hyk写算法了吗&#xff0c;一枚致力于学习算法和人工智能领域的小菜鸟。 &#x1f50e;个人主页&#xff1a;主页链接&#xff08;欢迎各位大佬光临指导&#xff09; ⭐️近…

Linux:DHCP服务配置

目录 一、DHCP概述以及DHCP的好处 1.1、概述 1.2、DHCP的好处 二、DHCP的模式与分配方式 2.1、模式 2.2、DHCP的分配方式 三、DHCP工作原理 四、安装DHCP服务 五、DHCP局部配置并且测试 5.1、subnet 网段声明 5.2、客户机预留指定的固定ip地址 一、DHCP概述以及DHCP…

【雷丰阳-谷粒商城 】【分布式高级篇-微服务架构篇】【21】【购物车】

持续学习&持续更新中… 守破离 【雷丰阳-谷粒商城 】【分布式高级篇-微服务架构篇】【21】【购物车】 购物车需求描述购物车数据结构数据Model抽取实现流程&#xff08;参照京东&#xff09;代码实现参考 购物车需求描述 用户可以在登录状态下将商品添加到购物车【用户购物…

归并排序的实现(递归与非递归)

概念 基本思想&#xff1a;归并排序&#xff08;MERGE-SORT&#xff09;是建立在归并操作上的一种有效的排序算法,该算法是采用分治法&#xff08;Divide andConquer&#xff09;的一个非常典型的应用。将已有序的子序列合并&#xff0c;得到完全有序的序列&#xff1b;即先使…

Java多线程不会?一文解决——

方法一 新建类如MyThread继承Thread类重写run()方法再通过new MyThread类来新建线程通过start方法启动新线程 案例&#xff1a; class MyThread extends Thread {public MyThread(String name) {super(name);}Overridepublic void run() {for(int i0;i<10;i){System.out.…

【qt】TCP 服务端怎么收到信息?

上一节,我已经讲了,TCP的监听,是基于上一节的,不知道的可以看看. 当我们的TCP 服务器 有 客户端请求连接的时候,会发出一个信号newConnection(). 在TCP服务端与客户端的通信中,我们需要使用到套接字 QTcpSocket类. 套接字相当于是网络通信的接口,服务段和客户端都要通过它进行通…

STM32-SPI和W25Q64

本内容基于江协科技STM32视频学习之后整理而得。 文章目录 1. SPI&#xff08;串行外设接口&#xff09;通信1.1 SPI通信简介1.2 硬件电路1.3 移位示意图1.4 SPI时序基本单元1.5 SPI时序1.5.1 发送指令1.5.2 指定地址写1.5.3 指定地址读 2. W25Q642.1 W25Q64简介2.2 硬件电路2…

MATLAB常用语句总结7

MATLAB总结7&#xff1a;常见错误归纳 本篇专门用于记录一些应试技巧 文章目录 MATLAB总结7&#xff1a;常见错误归纳前言一、一些小定义和小技巧二、蒙塔卡罗求解方法1.函数的定义2.函数引用3.代码量较少的蒙塔卡罗 三、函数引用与多变量四、矩阵引用五、非线性函数&#xff…

二叉树的链式存储

目录 链式存储&#xff1a; 简介&#xff1a; 二叉树链式存储的模拟实现&#xff1a; 节点的定义&#xff1a; ​编辑 链式二叉树的创建&#xff1a; 前序构建&#xff1a; 中序构建&#xff1a; 后续构建&#xff1a; 链式二叉树的销毁&#xff1a; 链式二叉树求节点…

algorithm算法库学习之——不修改序列的操作

algorithm此头文件是算法库的一部分。本篇介绍不修改序列的操作函数。 不修改序列的操作 all_ofany_ofnone_of (C11)(C11)(C11) 检查谓词是否对范围中所有、任一或无元素为 true (函数模板) for_each 应用函数到范围中的元素 (函数模板) for_each_n (C17) 应用一个函数对象到序…

Raw Socket(一)实现TCP三次握手

实验环境&#xff1a; Windows物理机&#xff1a;192.168.1.4 WSL Ubuntu 20.04.6 LTS&#xff1a;172.19.32.196 Windows下的一个http服务器&#xff1a;HFS&#xff0c;大概长这个样子&#xff1a; 客户端就是Ubuntu&#xff0c;服务端就是这个…