【Leetcode每日一题】 前缀和 - 和为 K 的子数组(难度⭐)(29)

1. 题目解析

题目链接:560. 和为 K 的子数组

这个问题的理解其实相当简单,只需看一下示例,基本就能明白其含义了。

核心在于计算题目所给数组是否存在连续子数组和为指定值,存在返回连续子数组个数即可,不存在返回0即可。

2.算法原理

要计算以数组中的位置i为结尾的和为k的子数组数量,我们首先需要理解前缀和的概念。sum[i]代表从数组起始位置到位置i(包括i)之间所有元素的和。为了找到这样的子数组,我们需要确定有多少起始位置x1, x2, x3, ...,使得从xi的区间内所有元素的和恰好为k

这意味着,如果我们考虑从位置0x(不包括x+1)的区间,其和应该是sum[i] - k。因此,问题转化为在[0, i - 1]的区间内,查找有多少个前缀和等于sum[i] - k

为了高效地解决此问题,我们不需要真的初始化一个前缀和数组,因为只关心在位置i之前,哪些前缀和的值等于sum[i] - k。因此,我们可以使用一个哈希表来跟踪在遍历数组时,每种前缀和出现的次数。这样,在遍历到位置i时,我们只需查看哈希表中键为sum[i] - k的值,这个值就代表了以位置i为结尾的和为k的子数组的数量。

总的来说,我们的策略是:

  1. 遍历数组,同时计算当前位置的前缀和。
  2. 使用哈希表来存储之前计算过的前缀和及其出现的次数。
  3. 在每个位置i,查找哈希表中键为sum[i] - k的值,该值即为以i为结尾的和为k的子数组数量。

 3.代码编写

class Solution {
public:
    int subarraySum(vector<int>& nums, int k) {
        unordered_map<int, int> hash;
        hash[0] = 1;
        int ret = 0, sum = 0;
        for(auto x : nums)
        {
            sum += x;
            if(hash.count(sum - k)) ret += hash[sum - k];
            hash[sum]++;
        }
        return ret;
    }
};

The Last

嗯,就是这样啦,文章到这里就结束啦,真心感谢你花时间来读。

觉得有点收获的话,不妨给我点个吧!

如果发现文章有啥漏洞或错误的地方,欢迎私信我或者在评论里提醒一声~ 

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

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

相关文章

C++基础2:C++基本数据类型和控制结构

此专栏为移动机器人知识体系下的编程语言中的 C {\rm C} C从入门到深入的专栏&#xff0c;参考书籍&#xff1a;《深入浅出 C {\rm C} C》(马晓锐)和《从 C {\rm C} C到 C {\rm C} C精通面向对象编程》(曾凡锋等)。 2.C基本数据类型和控制结构 2.1 C基本数据类型 程序是由算法…

HarmonyOS NEXT应用开发——Navigation开发 页面切换场景范例

简介 在应用开发时&#xff0c;我们常常遇到&#xff0c;需要在应用内多页面跳转场景时中使用Navigation导航组件做统一的页面跳转管理&#xff0c;它提供了一系列属性方法来设置页面的标题栏、工具栏以及菜单栏的各种展示样式。除此之外还拥有动态加载&#xff0c;navPathSta…

2024年最新Android大厂面试笔试题分享,大厂面试题汇总

随着互联网的发展&#xff0c;大众对程序员这个职业有了更多的了解&#xff0c;除了高薪工资之外&#xff0c;压力太大&#xff0c;黑白颠倒&#xff0c;作息不规律等等&#xff0c;也是身为一个程序员必须经历的事情。 大部分程序员都是安静的、稳重的&#xff0c;有什么问题…

算法简单试题

一、选择题 01.一个算法应该是( B ). A.程序 B.问题求解步骤的描述 C.要满足五个基本特性 D.A和C 02&#xff0e;某算法的时间复杂度为O(n)&#xff0c;则表示该…

探索AntDB:数据驱动时代的引擎

AntDB的发展道路一直如一条平稳而高效的航线&#xff0c;其升级过程始终是经过细致策划与多方验证。每一次的版本更新&#xff0c;都蕴含着团队的心血和智慧&#xff0c;保障系统的稳定与性能。AntDB在高速发展的同时&#xff0c;始终不忘稳扎稳打&#xff0c;为用户提供最优质…

基于java的宠物常规护理知识管理系统

项目源码&#xff1a;https://gitee.com/oklongmm/biye2 在设计一个宠物常规护理知识管理系统时&#xff0c;我们需要考虑系统的可扩展性&#xff0c;易用性和稳定性。以下是系统设计的功能模块&#xff1a; 一、用户模块&#xff1a; 1. 注册与登录&#xff1a;用户可以通过…

新书速览|软件性能测试、分析与调优实践之路(第2版)

性能调优理论和实践的完美结合&#xff0c;融合作者多年性能调优的经验&#xff0c;读者无须再为性能问题而发 本书内容 《软件性能测试、分析与调优实践之路&#xff08;第2版&#xff09;》主要分享作者在多年软件测试从业中积累的关于性能测试、分析诊断与调优技巧等方面的实…

全排列 全排列 II N皇后

46.全排列 力扣题目链接(opens new window) 给定一个 没有重复 数字的序列&#xff0c;返回其所有可能的全排列。 示例: 输入: [1,2,3]输出: [ [1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1] ] 递归终止条件&#xff1a;当收集元素的数组path的大小达到和nums数组…

Vue3和Vue2的相关面试知识点,一点要记住

Vue3 1、Vue2 和 Vue3 的区别&#xff1f; vue3 对于 typescript 的支持更加的好 vue3 的 Composition API&#xff0c; vue2 的 Option API vue3 打包使用 tree-shaking 策略&#xff0c;体积更小 vue3 在模板编译的阶段会有静态节点提升&#xff0c;运行时性能更好 vue3…

解码Transformer: 自注意力机制和TA的优化策略

注意力机制自从2014年被正式提出后&#xff0c;逐渐成为了NLP中应用最广泛的设计。借助简单而又变幻莫测的Attention机制&#xff0c;一系列横扫SOTA的模型被提出。自注意力机制&#xff08;Self-Attention&#xff09;&#xff0c;允许序列中的标记相互交互&#xff0c;并计算…

msvcr120.dll丢失怎样修复,更了解msvcr120.dll文件从而解决丢失问题

在电脑使用过程中&#xff0c;"msvcr120.dll丢失"是常见的错误提示之一。那么&#xff0c;今天就和大家聊聊msvcr120.dll文件&#xff0c;如果msvcr120.dll文件丢失的问题时什么原因导致的&#xff0c;让我们仔细来看一下msvcr120.dll是什么以及msvcr120.dll丢失怎样…

反射(重点)

1.反射的概述 Java给我们提供了一套API&#xff0c;使用这套API我们可以在运行时动态的获取指定对象所属的类&#xff0c;创建 运行时类的对象&#xff0c;调用指定的结构&#xff0c;(属性&#xff0c;方法)等 API&#xff1a; java.lang.Class&#xff1a;代表一个类 jav…

游戏力:竞技游戏设计实战教程

&#x1f482; 个人网站:【 海拥】【神级代码资源网站】【办公神器】&#x1f91f; 基于Web端打造的&#xff1a;&#x1f449;轻量化工具创作平台&#x1f485; 想寻找共同学习交流的小伙伴&#xff0c;请点击【全栈技术交流群】 游戏力&#xff1a;竞技游戏设计实战教程 引言…

高中数学:单调奇偶综合(较难)

一、奇偶性扩展 1、普通轴对称函数 要会根据抽象函数的关系&#xff0c;找出对称轴 简便记法&#xff1a;纵相等&#xff0c;对称轴 2、普通中心对称函数 要会找出对称中心点坐标 简便记法&#xff1a;纵和定&#xff0c;中心点 二、题型汇总 解题方法 抽象函数 1、…

社交媒体革新者:揭秘Facebook对在线互动的影响

1. Facebook的兴起与发展 Facebook由马克扎克伯格在哈佛大学宿舍创建&#xff0c;最初只是服务于哈佛大学学生的社交网络。然而&#xff0c;其后快速扩张到其他大学和全球&#xff0c;成为了全球最大的社交媒体平台之一。其发展历程不仅是数字时代的典范&#xff0c;也是创业成…

史上最大优惠!阿里云宣布全线降价99元一年,新老客户同享

2024阿里云服务器优惠活动政策整理&#xff0c;阿里云99计划ECS云服务器2核2G3M带宽99元一年、2核4G5M优惠价格199元一年&#xff0c;轻量应用服务器2核2G3M服务器61元一年、2核4G4M带宽165元1年&#xff0c;云服务器4核16G10M带宽26元1个月、149元半年&#xff0c;云服务器8核…

证件照制作繁琐?学会这三招轻松制作专业级证件照!

朋友们&#xff0c;您是否曾经为了办理各种证件、报名考试或者求职简历中的证件照而烦恼呢&#xff1f;是否希望能在家就能便捷高效地制作出符合规格的专业证件照&#xff1f;今天我将为大家推荐三款国内外备受好评的证件照处理工具&#xff0c;让您随时随地拥有完美证件照&…

AI领域再出“王炸“----Claude3是否会成为下一个“神“

目录 一.Claude3最新发布 二.Claude3支持20万token 三.Claude3在未公开算法上取得重大突破 1.Claude 3读懂博士论文 2.量子跃迁集成&#xff1a; Claude 3智商&#xff1a;101 测试方法 测试细节 通过Karpathy挑战 Claude 3自画像&#xff0c;突破本我 从洛杉矶排到…

蚂蚁感冒c++

题目 思路 “两蚂蚁碰面会掉头&#xff0c;若其中一只蚂蚁感冒了&#xff0c;会把感冒传染给碰到的蚂蚁”&#xff0c;这句话看作是“两蚂蚁碰面会互相穿过&#xff0c;只是把感冒的状态传给了另一只蚂蚁”&#xff0c;因为哪只蚂蚁感冒了并不是题目的重点&#xff0c;重点是有…

浅谈块存储、文件存储、对象存储

**块存储、文件存储和对象存储各自有其独特的特点和适用场景**。具体来说&#xff1a; 1. **块存储**&#xff1a; - 描述&#xff1a;块存储将存储空间分割成固定大小的块&#xff0c;这些块可以直接映射到主机操作系统。它提供的是原始的存储空间&#xff0c;不带文件系统…