在做题中学习(58):和为K的子数组

560. 和为 K 的子数组 - 力扣(LeetCode)

因为是判断子数组的和 + 要返回 == k  的次数,所以

解法:前缀和 + 哈希表

提出一个概念:以下标i为结尾的所有子数组

那要找出所有和 == k的子数组 就相当于:找出所有值为dp[i] - k的子数组。

 dp[i] - k就是一段区间的前置和了,只要把所有以下标i为结尾的所有子数组的前缀和丢到哈希表中,最后返回 dp[i] - k (前提:要存在)出现的次数即可。

细节

1.前缀和什么时候丢入哈希表?

因为放进去的是前缀和,放[0,i]的话,到了[0,i+1]就会重复,所以到i下标时,先放入[0,i-1]的前缀和,再加入自己。(dp[i])

2.不用真的创建一个前缀和数组

dp[i] = sum + nums[i]  ,所以只需要一个sum代表前一次的前缀和,每次算完前缀和,把sum更新就行了。

3.如果到自己的前缀和是k呢?(dp[i] == k)

那范围就是:[0,-1],显然不行,所以默认让hash[0] = 1

class Solution 
{
public:int subarraySum(vector<int>& nums, int k) {unordered_map<int,int> hash;hash[0] = 1;int sum = 0,count = 0;for(auto e : nums){sum += e;if(hash.count(sum-k))count += hash[sum - k];//存完[0,i-1]后,再存自己hash[sum]++;}return count;}
};

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

如若内容造成侵权/违法违规/事实不符,请联系一条长河网进行投诉反馈,一经查实,立即删除!

相关文章

[Cesium for Supermap]加载iserver发布的wms服务

1&#xff0c;wms服务 2&#xff0c;加载代码 let provider new Cesium.WebMapServiceImageryProvider({url: "http://support.supermap.com.cn:8090/iserver/services/map-china400/wms111/China_4326",enablePickFeatures:true,rectangle: Cesium.Rectangle.fromD…

dbeaver 链接 Oceanbase 数据库,dbeaver安装数据库驱动

新增驱动 提前到Oceanbase官网下载好驱动 1、点击数据库 -> 驱动管理器 -> 新建 2、添加驱动文件 联接数据库 1、选择你添加的驱动 2、测试

【OpenHarmony IDL工具规格及使用说明书】

OpenHarmony IDL工具规格及使用说明书 IDL接口描述语言简介 当客户端和服务器进行IPC通信时&#xff0c;需要定义双方都认可的接口&#xff0c;以保障双方可以成功通信&#xff0c;OpenHarmony IDL&#xff08;OpenHarmony Interface Definition Language&#xff09;则是一种…

【Apache Doris】周FAQ集锦:第 3 期

【Apache Doris】周FAQ集锦&#xff1a;第 3 期 SQL问题数据操作问题运维常见问题其它问题关于社区 欢迎查阅本周的 Apache Doris 社区 FAQ 栏目&#xff01; 在这个栏目中&#xff0c;每周将筛选社区反馈的热门问题和话题&#xff0c;重点回答并进行深入探讨。旨在为广大用户和…

[AI]-(第1期):OpenAI-API调用

文章目录 一、OpenAI API中使用GPT-3.5-turbo模型充值方式使用模型计费方式价格说明相关限制和条款 二、接入一个OpenAI API流程1. 获取OpenAI API 密钥2. 集成ChatGPT到小程序3. 处理用户输入4. 调用OpenAI API5. 返回回复至小程序6. 持续优化7. Postman请求示例 三、通用AI客…

河南广电与LiblibAI签署战略合作协议

5月15日&#xff0c;河南广电科技与LiblibAI战略签约仪式在郑州中原福塔新闻发布厅隆重举行。双方将本着“共商、共享、共建、共赢”原则&#xff0c;基于全面、可持续的战略合作伙伴关系&#xff0c;发挥各自优势&#xff0c;共同聚焦生成式AI领域&#xff0c;围绕内容创作、商…

内网环境ubuntu设置静态ip、DNS、路由,不影响网络访问

内网环境通常是有线的&#xff0c;通过服务器的ip、mac、dns地址访问网络才生效的&#xff0c;如果ip地址变了&#xff0c;就不能访问网络了。 如果你的ip地址变了&#xff0c;或者要防止ip变更影响网络访问&#xff0c;就要设置 1、依次点击右上角的电源-设置&#xff0c;在打…

如何管理测试用例?测试用例有什么管理工具?YesDev

3.1 测试用例 测试用例(Test Case) 是指对一项特定的软件产品进行测试任务的描述&#xff0c;体现测试方案、方法、技术和策略。其内容包括测试目标、测试环境、输入数据、测试步骤、预期结果等。简单地认为&#xff0c;测试用例是为某个特殊目标而编制的一组测试输入、执行条…

源代码防泄漏之沙盒技术分析

随着企业信息化的快速发展&#xff0c;对于单位来说&#xff0c;网络中包含了很多重要的信息资料&#xff0c;比如网络中积累和掌握了大量的研发数据、生产数据和运营信息等&#xff0c;组织不希望这些资料离开企业内部的网络环境&#xff0c;甚至不允许在网络外部传递与交流&a…

工单系统有哪些?

市面上的工单系统真的非常多&#xff0c;一个个列举肯定说不完&#xff0c;我大致给它们按照不同的依据&#xff0c;进行了一下分类&#xff1a; 1、按部署方式分类&#xff1a; 本地化部署工单系统&#xff1a;适用于对数据安全性要求较高的企业&#xff0c;需要企业在本地服…

[笔试训练](二十三)067:打怪068:字符串分类069:城市群数量

目录 067:打怪 068:字符串分类 069:城市群数量 067:打怪 题目链接:打怪 (nowcoder.com) 题目&#xff1a; 题解&#xff1a; 直接计算结果&#xff1a; 1.一只怪物能抗几次攻击 int m(H/a)(H%a0?0:1); 2.杀死一只怪物&#xff0c;玩家要抗几次攻击 int nm-1; *3.杀死一只…

代码随想录训练营Day 29|力扣39. 组合总和、40.组合总和II、131.分割回文串

1.组合总和 题目链接/文章讲解&#xff1a; 代码随想录 视频讲解&#xff1a;带你学透回溯算法-组合总和&#xff08;对应「leetcode」力扣题目&#xff1a;39.组合总和&#xff09;| 回溯法精讲&#xff01;_哔哩哔哩_bilibili 代码&#xff1a;&#xff08;未剪枝版 &#xf…

ue引擎游戏开发笔记(38)——实现敌人接收攻击伤害,并作出反应

1.需求分析&#xff1a; 现在已经显示造成实际伤害&#xff0c;但敌人对实际伤害并未产生反馈&#xff0c;例如还击&#xff0c;或者死亡倒地等等&#xff0c;实现敌人对于受击的反馈。 2.操作实现&#xff1a; 1.思路&#xff1a;在动画蓝图中添加死亡动画&#xff0c;并通过…

惠普打印机无线网络连接设置

休息一下&#xff0c;灌个水。这次没多少内容&#xff0c;具体步骤惠普官网上都有&#xff0c;唯一增加的是对安装过程中踩的坑做了一个说明。 一&#xff0e;打印机无线网络连接设置步骤 惠普打印机设置无线网络连接&#xff0c;共16个步骤。 1. 在电脑上打开任意浏览器&am…

速度与激情:Redis如何以核心数据结构驱动极致性能

关注微信公众号 “程序员小胖” 每日技术干货&#xff0c;第一时间送达&#xff01; 引言 Redis是一个开源的内存数据结构存储系统&#xff0c;它支持多种类型的数据结构&#xff0c;如字符串、散列、列表、集合、有序集合等。Redis以其出色的性能和低延迟特性而闻名&#xf…

全网最简单的Mysql 8.3 安装及环境配置教程

Windows系统计算机环境配置 第一篇关于环境配置的文档之MySQL 8.3&#xff08;msi版本和zip版本略有不同&#xff0c;本文档介绍msi版本&#xff0c;若zip版本有需求&#xff0c;请在评论区留言&#xff0c;我后续会出相关文档。&#xff09; 前言 网上的MySQL配置教程非常多…

电脑常用的PDF阅读器-嗨动PDF编辑器!带你详细了解它

电脑常用的PDF阅读器-嗨动PDF编辑器&#xff01;在数字化信息爆炸的时代&#xff0c;PDF格式的文件因其易于打印和保留原始格式等优点&#xff0c;成为了人们日常工作和学习的常用格式。而对于PDF文件的处理&#xff0c;一款功能强大、操作简便的PDF阅读器是必不可少的。今天&a…

合并K个升序链表

题目 解法一 优先级队列 思想 将每个链表中的一个节点存放到优先级队列中&#xff0c;本题采用小根堆&#xff0c;将小根堆中的根节点取出&#xff0c;插入到最终的链表中&#xff0c;并且将该节点在原链表中的下一个节点插入小根堆中&#xff08;需要向下调整&#xff09;&a…

【练习】分治--快排思想

&#x1f3a5; 个人主页&#xff1a;Dikz12&#x1f525;个人专栏&#xff1a;算法(Java)&#x1f4d5;格言&#xff1a;吾愚多不敏&#xff0c;而愿加学欢迎大家&#x1f44d;点赞✍评论⭐收藏 目录 颜色分类 题目描述 题解 代码实现 排序数组 题目描述 题解 代码…

华为正式放弃高通芯片 | 百能云芯

5月15日&#xff0c;据外媒最新报道&#xff0c;高通公司正式确认&#xff0c;华为已无需依赖其处理器供应。 在出口许可被正式吊销前&#xff0c;高通的首席财务官已公开表示&#xff0c;预计明年与华为之间的芯片销售将为零&#xff0c;因为华为决定不再从高通购买4G芯片。 报…