当前位置: 首页 > news >正文

[100天算法】-和为 K 的子数组(day 39)

题目描述

给定一个整数数组和一个整数 k,你需要找到该数组中和为 k 的连续的子数组的个数。示例 1 :输入:nums = [1,1,1], k = 2
输出: 2 , [1,1] 与 [1,1] 为两种不同的情况。
说明 :数组的长度为 [1, 20,000]。
数组中元素的范围是 [-1000, 1000] ,且整数 k 的范围是 [-1e7, 1e7]。来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/subarray-sum-equals-k
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

方法 1:前缀和

思路

比较直白的想法是,先构建前缀和数组 prefix,计算以 i 结束的子数组的和,然后在这个数组中找到所有满足条件的 [i, j] 区间,也就是 prefix[j] - prefix[i] 等于 K。但这样找得两层循环了,时间复杂度比较高。

有没有只需要遍历一遍数组的方法呢?其实只要算一点点数学就好了:

  • 我们要找的一段区间 [i, j] 需要满足 prefix[j] - prefix[i] == k (i < j)。
  • 也就是当我们在遍历到 j 这个位置的时候,只要往 j 的左边去找到有没有 prefix[i] 等于 prefix[j] - k 就行,满足条件的 prefix[i] 可能有一个或多个哦。
  • 在遍历到 j 之前,我们已经遍历过 i 了 (i < j),所以我们只需要在遍历到 i 的时候用一个哈希表把 prefix[i] 存起来,就能实现 O(1) 时间的查找。

其实我们连 prefix 数组都不需要,因为我们在算出一个前缀和的时候,就已经把它存到哈希表里面去了。所以可以只用一个变量 prefix 来计算前缀和,在遍历 nums 数组的过程中不断更新 prefix,同时检查 map[prefix - k] 是否在之前出现过。

复杂度分析

  • 时间复杂度:$O(n)$, n 为数组长度,只扫描了一次数组。
  • 空间复杂度:$O(n)$, n 为数组长度,使用了一个哈希表来存每个前缀和出现的次数。

代码

JavaScript Code

/*** @param {number[]} nums* @param {number} k* @return {number}*/
var subarraySum = function (nums, k) {const map = {};let count = 0;let prefix = 0;map[prefix] = 1;for (let i = 0; i < nums.length; i++) {prefix += nums[i];if (prefix - k in map) {count += map[prefix - k];}map[prefix] = (map[prefix] || 0) + 1;}return count;
};

相关文章:

[100天算法】-和为 K 的子数组(day 39)

题目描述 给定一个整数数组和一个整数 k&#xff0c;你需要找到该数组中和为 k 的连续的子数组的个数。示例 1 :输入:nums [1,1,1], k 2 输出: 2 , [1,1] 与 [1,1] 为两种不同的情况。 说明 :数组的长度为 [1, 20,000]。 数组中元素的范围是 [-1000, 1000] &#xff0c;且整…...

Leo赠书活动-02期 【信息科技风险管理:合规管理、技术防控与数字化】

✅作者简介&#xff1a;大家好&#xff0c;我是Leo&#xff0c;热爱Java后端开发者&#xff0c;一个想要与大家共同进步的男人&#x1f609;&#x1f609; &#x1f34e;个人主页&#xff1a;Leo的博客 &#x1f49e;当前专栏&#xff1a; 赠书活动专栏 ✨特色专栏&#xff1a;…...

L2-026 小字辈 - java

L2-026 小字辈 时间限制 400 ms 内存限制 64 MB 题目描述&#xff1a; 本题给定一个庞大家族的家谱&#xff0c;要请你给出最小一辈的名单。 输入格式&#xff1a; 输入在第一行给出家族人口总数 N&#xff08;不超过 100 000 的正整数&#xff09; —— 简单起见&#xff0c…...

排序算法-堆积树排序法(HeapSort)

目录 排序算法-堆积树排序法&#xff08;HeapSort&#xff09; 1、说明 2、算法分析 3、C代码 排序算法-堆积树排序法&#xff08;HeapSort&#xff09; 1、说明 堆积树排序法是选择排序法的改进版&#xff0c;可以减少在选择排序法中的比较次数&#xff0c;进而减少排序…...

名词解释 MongoDB

MongoDB 是一个面向文档的数据库管理系统&#xff0c;它不使用传统的表格结构&#xff0c;而是将数据组织成类似文档的形式&#xff0c;通常使用JSON格式。 文档数据库&#xff1a;数据以文档的形式存储&#xff0c;每个文档可以包含不同的字段&#xff0c;就像一个文件可以包…...

Look Back(cf div3 905)

题意&#xff1a;给你一个长度为n&#xff08;(1≤n≤10^5)数组a[]&#xff0c;你可以进行一个操作 使a[i]a[i]*2,问最少经过多少次这样的操作使的a[]不递减,a[i]>a[i-1]。 输入样例&#xff1a; 6 1 1 2 1 1 3 1 2 1 4 2 3 2 1 5 4 5 4 5 4 10 1 7 7 2 3 4 3 2 1 100 输出…...

Spring框架的发展历程

Spring框架的发展历程 自2004年以来&#xff0c;Spring框架已经成为Java开发人员最受欢迎的开源框架之一。它提供了一个全面的编程和配置模型&#xff0c;旨在简化企业级Java应用程序的开发过程。本文将详细介绍Spring框架的发展历程&#xff0c;以及它如何为Java开发人员提供…...

vue 级联查询5级--省/市/区/街道/社区

<template> <div> 1234 <el-select v-model="provinceVal" @change="selectProvinceFn" placeholder="请选择"> <el-option v-for="item in provinceList" :key="item.code" :label="item.name&q…...

C++并发与多线程(8) | 互斥量

一、互斥量(mutex)的基本概念 互斥量(Mutex)是一种用于多线程编程的同步机制,用于管理共享资源的访问,以确保线程之间不会同时访问某个共享资源,从而避免竞态条件(Race Condition)和数据损坏。下面是互斥量的基本概念: 互斥性(Mutual Exclusion):互斥量用于确保一…...

Power BI 傻瓜入门 3. 选择Power BI的版本

本章内容包括&#xff1a; Excel与Power BI的比较选择Power BI的桌面版和服务版之间的差异了解Microsoft提供的许可选项 挑选正确版本的Power BI可能就像参观世界上最大的糖果店&#xff1a;你可以从许多细微差别的替代品中进行选择。选择可以归结为想要、需要、规模&#xf…...

BadNets:基于数据投毒的模型后门攻击代码(Pytorch)以MNIST为例

加载数据集 # 载入MNIST训练集和测试集 transform transforms.Compose([transforms.ToTensor(),]) train_loader datasets.MNIST(rootdata,transformtransform,trainTrue,downloadTrue) test_loader datasets.MNIST(rootdata,transformtransform,trainFalse) # 可视化样本 …...

freeRTOS内部机制——栈的作用

上图中*pa 和*pb分别为R0&#xff0c;R1&#xff0c;调用C函数时&#xff0c;第一个参数保存在R0中第二个参数保存在R1中。这是约定。 指令保存在哪里&#xff1f; 指令保存在flash上面 LR等于什么? LR是返回地址&#xff0c;函数执行完了过后LR等于下一条指令的地址 运行…...

python 桌面软件开发-matplotlib画图鼠标缩放拖动

继上一篇在 Java 中缩放拖动图片后&#xff0c;在python matplotlib中也来实现一个自由缩放拖动的例子&#xff1a; python matplotlib 中缩放&#xff0c;较为简单&#xff0c;只需要通过设置要显示的 x y坐标的显示范围即可。基于此&#xff0c;实现一个鼠标监听回调&#xf…...

【JavaScript基础】JavaScript头等函数的理解

彻底理解JavaScript头等函数 一、函数的理解 &#x1f525; 什么是函数&#xff1f; 一般来说&#xff0c;一个函数是可以通过外部代码 调用 的一个“子程序”&#xff08;或在递归的情况下由内部函数调用&#xff09;。像程序本身一样&#xff0c;一个函数由称为函数体的一…...

如何把项目上传到Gitee(详细教程)

找到项目根目录右键打开Git Bash Here 输入命令&#xff1a;git init 回车 输入命令&#xff1a;git status 输入命令&#xff1a;git add . 输入命令&#xff1a;git status git commit -m 项目描述 在Gitee官网注册好账号后&#xff0c;git 新建项目 填写补充git项目信息及…...

Ubuntu挂载windows下的共享文件夹

Ubuntu挂载windows下的共享文件夹 更新apt源 如果出现安装失败&#xff0c;需要更新apt源为阿里云 # 备份原始文件 sudo cp /etc/apt/sources.list.d/* /etc/apt/sources.list.d.bak/# 修改文件内容 sudo vim /etc/apt/sources.list# 替换内容为如下 deb https://mirrors.al…...

什么是WMS系统条码化管理

WMS系统是一种用于仓库管理的信息化系统&#xff0c;旨在提高仓库操作的效率和准确性。而在WMS系统中&#xff0c;条码化管理是一项关键的技术和方法&#xff0c;它通过将商品和物料打上条码&#xff0c;并利用扫描设备进行数据采集和处理&#xff0c;实现了仓库管理的全面自动…...

【云原生之kubernetes实战】在k8s环境下部署moredoc文库系统

【云原生之kubernetes实战】在k8s环境下部署moredoc文库系统 一、moredoc介绍1.1 moredoc简介1.2 moredoc技术栈二、本次实践介绍2.1 本次实践简介2.2 本次环境规划三、检查k8s环境3.1 检查工作节点状态3.2 检查系统pod状态四、创建mysql的secret资源4.1 创建部署目录4.2 创建密…...

[Database] MySQL 8.x Window / Partition Function (窗口/分区函数)

&#x1f9f2;相关文章 [1] MySQL 系统表解析以及各项指标查询 [2] MySQL 5.7 JSON 字段的使用的处理 [3] MySQL经典练习50题 简介 MySQL 8.0版本开始支持窗口函数 官方文档 在之前的版本中已存在的大部分聚合函数&#xff0c;在MySQL 8 中也可以作为窗口函数来使用 方法 / …...

openGauss Meetup(天津站)精彩回顾 | openGauss天津用户组正式成立

由openGauss社区、天开发展集团、天津市软件行业协会、天大智图&#xff08;天津&#xff09;科技有限公司联合主办的“openGauss Meetup • 天津站”已于10月13日落下帷幕&#xff0c;此次活动邀请到众多业内技术专家&#xff0c;从技术创新、学术创新、发展创新、以及生态共建…...

Anthropic泄露新一代Claude Mythos 模型,具备网络安全漏洞检测优势

配置错误曝光新模型Anthropic PBC 内容管理系统的一处配置错误意外泄露了其正在测试的新型大语言模型 Claude Mythos。该公司周四向《财富》杂志证实&#xff0c;工程师已完成该模型的训练工作&#xff0c;目前正与早期客户进行试点测试。Anthropic 强调这是其"迄今为止构…...

保姆级教程:小米AX3000T刷OpenWrt 24.10.0全流程(含救砖指南)

小米AX3000T路由器刷OpenWrt全流程实战指南 作为一名长期折腾家用路由器的技术爱好者&#xff0c;我最近刚完成了小米AX3000T刷OpenWrt的全过程。相比官方固件&#xff0c;OpenWrt提供了更强大的自定义功能和性能优化空间。本文将分享从准备工作到救砖方案的完整经验&#xff…...

Linux文件IO编程实战:用GEC6818开发板上的C程序玩转open/read/write/lseek

Linux文件IO编程实战&#xff1a;GEC6818开发板上的C语言文件操作精要 在嵌入式Linux开发中&#xff0c;文件操作是最基础也是最重要的技能之一。GEC6818作为一款广泛应用于教学和工业场景的开发板&#xff0c;其Linux系统编程能力尤为关键。本文将带你深入理解Linux"一切…...

从RNN到Mamba:一个算法工程师的‘长文本’建模踩坑与选型指南

从RNN到Mamba&#xff1a;一个算法工程师的‘长文本’建模踩坑与选型指南 当处理长达数万token的日志序列时&#xff0c;传统RNN的梯度消失问题让模型难以捕捉跨时段的异常模式&#xff0c;而Transformer的二次方复杂度又让显存迅速耗尽。这种困境促使我开始系统评估结构化状态…...

【单片机实战】中断服务程序编写精要:从现场保护到中断返回

1. 中断服务程序的核心作用与基本结构 第一次接触单片机中断时&#xff0c;我盯着开发板上的按键发愣——明明没有循环检测IO口状态&#xff0c;按下按键却能立即触发LED亮灭。这种"随叫随到"的响应机制&#xff0c;就是中断服务程序&#xff08;ISR&#xff09;的魔…...

网络电台个性化高效管理:foobox-cn技术实现与应用指南

网络电台个性化高效管理&#xff1a;foobox-cn技术实现与应用指南 【免费下载链接】foobox-cn DUI 配置 for foobar2000 项目地址: https://gitcode.com/GitHub_Trending/fo/foobox-cn foobox-cn作为foobar2000的DUI配置方案&#xff0c;通过创新的电台管理系统架构&…...

让 TDengine 在 JetBrains IDEs 里更像“原生数据库”一点

让 TDengine 在 JetBrains IDEs 里更像“原生数据库”一点 Author: ChangJin Wei (魏昌进) 最近我做了一个小插件&#xff0c;把 TDengine 接入到了 JetBrains IDEs 的数据库工具链里。 先埋个小提示&#xff1a;文末有彩蛋。 项目地址&#xff1a; GitHub: https://github.…...

文脉定序系统处理多语言语义排序实战:跨语言检索效果展示

文脉定序系统处理多语言语义排序实战&#xff1a;跨语言检索效果展示 你有没有遇到过这样的烦恼&#xff1f;想找一份关于“机器学习”的日文资料&#xff0c;却只能用中文关键词去搜&#xff0c;结果要么搜不到&#xff0c;要么搜出来的东西完全不对路。或者&#xff0c;你手…...

从 0 手写一个巡检调度系统(五):接入大模型实现巡检问题解读与修复建议

摘要&#xff1a;在既有「架构巡检 → 问题落库」链路中&#xff0c;第一次引入大模型能力&#xff1a;对单条 issue 做「解读 修复建议」&#xff0c;要求输出可解析的结构化 JSON 并落库可追溯。本文记录选型、配置、HTTP 客户端、Prompt 约束与踩坑&#xff0c;便于同类业务…...

Unity内联序列化类的秘密

一个藏在Inspector面板背后的"俄罗斯套娃" 一、开篇:一个看似简单的问题 你在Unity中写了一个脚本: public class Player : MonoBehaviour {public int health;public float speed...