560.和为K的子数组

560.和为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

暴力方法就不多说了,二重循环解决。

我说一下时间复杂度为O(n)的算法:

其实我们求这个所谓的子数组k,肯定累计计算前n项和,每次我们记忆化存储前n项和,键为前n项目和,值为对应该和出现的次数

满足子数列和为k翻译一下就是,总结前n项和减去k,看这样的结果是否有被记忆化存储,然后累计其次数即可,

当然,初始时我们设置一个{0,1},表明默认有一个前n项和为0的情况

参考代码

/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number}
 */
var subarraySum = function(nums, k) {
    const map = new Map();
    map.set(0, 1);
    let count = 0, pre = 0;
    for(const x of nums) {
        pre += x;
        if(map.has(pre - k))
            count+= map.get(pre - k)
        if(map.has(pre))
            map.set(pre, map.get(pre) + 1);
        else 
            map.set(pre, 1);
    }
    return count;
};

传统节目

在这里插入图片描述

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

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

线程池参数该怎么配置才能充分压榨CPU?

&#x1f3c3;‍♂️ 微信公众号: 朕在debugger© 版权: 本文由【朕在debugger】原创、需要转载请联系博主&#x1f4d5; 如果文章对您有所帮助&#xff0c;欢迎关注、点赞、转发和订阅专栏&#xff01; 目标 配置好线程池参数&#xff0c;压榨CPU&#xff0c;资本家看了都…

云备份day03

&#x1f4df;作者主页&#xff1a;慢热的陕西人 &#x1f334;专栏链接&#xff1a;C云备份项目 &#x1f4e3;欢迎各位大佬&#x1f44d;点赞&#x1f525;关注&#x1f693;收藏&#xff0c;&#x1f349;留言 主要内容介绍了第三方库httplib的一些内容&#xff0c;以及实现…

易宝OA getStockInRequestPrintDetail SQL注入漏洞复现

0x01 产品简介 易宝OA系统是一种专门为企业和机构的日常办公工作提供服务的综合性软件平台,具有信息管理、 流程管理 、知识管理(档案和业务管理)、协同办公等多种功能。 0x02 漏洞概述 易宝OA getStockInRequestPrintDetail 接口处存在SQL注入漏洞,未经身份认证的攻击者…

Promise和async/await

Promise是异步编程的一种解决方案&#xff0c;用来解决多层回调嵌套的问题。它的构造函数是同步执行的&#xff0c;then 方法是异步执行的&#xff0c;所以创建后里面的函数会立即执行&#xff0c;构造函数中的resolve和reject只有第一次执行有效&#xff0c;也就是说Promise状…

随手集☞MySQL部分知识盘点(loading。。。)

字段类型 数值类型 INT: 整数类型&#xff0c;可以是正数或负数。根据显示宽度和是否有符号&#xff0c;其范围会有所不同。TINYINT: 非常小的整数。SMALLINT: 小的整数。MEDIUMINT: 中等大小的整数。BIGINT: 大整数。FLOAT: 单精度浮点数。DOUBLE: 双精度浮点数。DECIMAL(M,N…

Oracle的物理结构解析

这些图是我自己画的&#xff0c;我也会在我的公众号【会用数据库】解析。理解起来非常简单&#xff0c;而且非常好记。不用死记硬背&#xff0c;有兴趣可以来公众号看呀。

GitOps - 为 OpenShift GitOps 配置邮件通知

《OpenShift 4.x HOL教程汇总》 说明&#xff1a;本文已经 在OpenShift 4.15 OpenShift GitOps 1.11.2 环境中验证 文章目录 ArgoCD 的 Notification 功能简介启动 OpenShift GitOps 的 Notification 功能配置邮件通知验证参考 说明&#xff1a;先根据《OpenShift 4 之 GitOp…

Peter算法小课堂—树状数组

大家好&#xff0c;我是人见人爱&#xff0c;花见花开&#xff0c;车见车爆胎的树状数组Peter Pan&#xff0c;hhh 讲正文前&#xff0c;先来一个长文警告⚠很重要的知识点&#xff1a;L SB&#xff08;SB&#xff1f;&#xff09; LSB 怎么算呢&#xff1f; 哦……懂了&…

环形链表2--绝妙的运算

一、要求 给定一个链表的头节点 head &#xff0c;返回链表开始入环的第一个节点。 如果链表无环&#xff0c;则返回 null。 如果链表中有某个节点&#xff0c;可以通过连续跟踪 next 指针再次到达&#xff0c;则链表中存在环。 为了表示给定链表中的环&#xff0c;评测系统…

静态路由协议实验综合实验

需求&#xff1a; 1、除R5的换回地址已固定外&#xff0c;整个其他所有的网段基于192.168.1.0/24进行合理的IP地址划分。 2、R1-R4每台路由器存在两个环回接口&#xff0c;用于模拟连接PC的网段&#xff1b;地址也在192.168.1.0/24这个网络范围内。 3、R1-R4上不能直接编写到…

机器学习KNN最邻近分类算法

文章目录 1、KNN算法简介2、KNN算法实现2.1、调用scikit-learn库中KNN算法 3、使用scikit-learn库生成数据集3.1、自定义函数划分数据集3.2、使用scikit-learn库划分数据集 4、使用scikit-learn库对鸢尾花数据集进行分类5、什么是超参数5.1、实现寻找超参数5.2、使用scikit-lea…

【vite】

目录 vite介绍vite的基础应用vite创建项目vite创建vue3项目vite创建vue2项目vite创建react项目 vite中使用css的各种功能vite中使用ts vite介绍 一、特点&#xff1a; 开发时效率极高开箱即用&#xff0c;功能完备摄取丰富&#xff0c;兼容rollup超高速热重载预设应用和类库打…

vulhub中 Struts2-015 远程代码执行漏洞复现

影响版本: 2.0.0 - 2.3.14.2 ## 原理与测试 漏洞产生于配置了 Action 通配符 *&#xff0c;并将其作为动态值时&#xff0c;解析时会将其内容执行 OGNL 表达式&#xff0c;例如&#xff1a; xml <package name"S2-015" extends"struts-default"> …

上位机图像处理和嵌入式模块部署(qmacvisual之n点标定)

【 声明&#xff1a;版权所有&#xff0c;欢迎转载&#xff0c;请勿用于商业用途。 联系信箱&#xff1a;feixiaoxing 163.com】 工业场景中&#xff0c;很多时候图像是用来做测量的。虽然我们很希望载台是平的&#xff0c;摄像头是正对着拍摄物体的&#xff0c;但是运行时间长…

可视化图表:象形柱图,比柱图漂亮、有趣100倍。

一、什么是象形柱图 象形柱图&#xff08;Pictorial Bar Chart&#xff09;是一种可视化图表&#xff0c;它使用图形或图片代替传统的矩形柱子来表示数据。每个图形或图片的大小和形状都与对应的数据值相关联&#xff0c;从而形成一种视觉上的象征性表示。 象形柱图通常用于展…

【每日刷题】Day3

【每日刷题】Day3 &#x1f955;个人主页&#xff1a;开敲&#x1f349; &#x1f525;所属专栏&#xff1a;每日刷题&#x1f34d; 目录 1. 69. x 的平方根 - 力扣&#xff08;LeetCode&#xff09; 2. 70. 爬楼梯 - 力扣&#xff08;LeetCode&#xff09; 3. 118. 杨辉三…

STL容器(3)

1,stack容器 1.1 基本概念 概念&#xff1a;stack是一种先进后出的数据结构&#xff0c;它只有一个出口 因此&#xff1a; 栈中只有顶端的元素才可以被使用&#xff0c;因此占不允许有遍历行为 栈中进入数据称为--入栈&#xff08;push) 栈中弹出数据称为--出栈&#xff08…

【Linux】虚拟机连不上外网 (1),2024百度网络安全岗面试真题收录解析

vi /etc/sysconfig/network-scripts/ifcfg-ens33 BOOTPROTOstatic ONBOOTyes IPADDR? NETMASK? GATEWAY? dns18.8.8.8 dns1144.144.144.144 这两个必填 自我介绍一下&#xff0c;小编13年上海交大毕业&#xff0c;曾经在小公司待过&#xff0c;也去过华为、OPPO等大厂…

深入理解Armv9 DSU-110中的L3 cache

快速链接: 【精选】ARMv8/ARMv9架构入门到精通-[目录] &#x1f448;&#x1f448;&#x1f448; 关键词&#xff1a; DynamIQ cluster、DSU-110、DSU-120、DSU、cache、mmu、缓存、高速缓存、内存管理、MPAM 思考&#xff1a; 1、L1、L2、L3 cache的替换策略是怎样的&#xff…

Android中的aidl接口及案例说明

目录 一、什么是AIDL 二、AIDL语法规格 三、AIDL实例 客户端: 服务端: 一、什么是AIDL AIDL,即 Android Interface Definition Language,用于android不同进程间通信接口。同一个应用里面还是建议用正常接口实现功能即可。 官方说明:Android 接口定义语言 (AIDL) | …