当前位置: 首页 > 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;从技术创新、学术创新、发展创新、以及生态共建…...

XML Group端口详解

在XML数据映射过程中&#xff0c;经常需要对数据进行分组聚合操作。例如&#xff0c;当处理包含多个物料明细的XML文件时&#xff0c;可能需要将相同物料号的明细归为一组&#xff0c;或对相同物料号的数量进行求和计算。传统实现方式通常需要编写脚本代码&#xff0c;增加了开…...

(LeetCode 每日一题) 3442. 奇偶频次间的最大差值 I (哈希、字符串)

题目&#xff1a;3442. 奇偶频次间的最大差值 I 思路 &#xff1a;哈希&#xff0c;时间复杂度0(n)。 用哈希表来记录每个字符串中字符的分布情况&#xff0c;哈希表这里用数组即可实现。 C版本&#xff1a; class Solution { public:int maxDifference(string s) {int a[26]…...

SciencePlots——绘制论文中的图片

文章目录 安装一、风格二、1 资源 安装 # 安装最新版 pip install githttps://github.com/garrettj403/SciencePlots.git# 安装稳定版 pip install SciencePlots一、风格 简单好用的深度学习论文绘图专用工具包–Science Plot 二、 1 资源 论文绘图神器来了&#xff1a;一行…...

相机从app启动流程

一、流程框架图 二、具体流程分析 1、得到cameralist和对应的静态信息 目录如下: 重点代码分析: 启动相机前,先要通过getCameraIdList获取camera的个数以及id,然后可以通过getCameraCharacteristics获取对应id camera的capabilities(静态信息)进行一些openCamera前的…...

实现弹窗随键盘上移居中

实现弹窗随键盘上移的核心思路 在Android中&#xff0c;可以通过监听键盘的显示和隐藏事件&#xff0c;动态调整弹窗的位置。关键点在于获取键盘高度&#xff0c;并计算剩余屏幕空间以重新定位弹窗。 // 在Activity或Fragment中设置键盘监听 val rootView findViewById<V…...

【7色560页】职场可视化逻辑图高级数据分析PPT模版

7种色调职场工作汇报PPT&#xff0c;橙蓝、黑红、红蓝、蓝橙灰、浅蓝、浅绿、深蓝七种色调模版 【7色560页】职场可视化逻辑图高级数据分析PPT模版&#xff1a;职场可视化逻辑图分析PPT模版https://pan.quark.cn/s/78aeabbd92d1...

浪潮交换机配置track检测实现高速公路收费网络主备切换NQA

浪潮交换机track配置 项目背景高速网络拓扑网络情况分析通信线路收费网络路由 收费汇聚交换机相应配置收费汇聚track配置 项目背景 在实施省内一条高速公路时遇到的需求&#xff0c;本次涉及的主要是收费汇聚交换机的配置&#xff0c;浪潮网络设备在高速项目很少&#xff0c;通…...

嵌入式学习笔记DAY33(网络编程——TCP)

一、网络架构 C/S &#xff08;client/server 客户端/服务器&#xff09;&#xff1a;由客户端和服务器端两个部分组成。客户端通常是用户使用的应用程序&#xff0c;负责提供用户界面和交互逻辑 &#xff0c;接收用户输入&#xff0c;向服务器发送请求&#xff0c;并展示服务…...

云原生安全实战:API网关Kong的鉴权与限流详解

&#x1f525;「炎码工坊」技术弹药已装填&#xff01; 点击关注 → 解锁工业级干货【工具实测|项目避坑|源码燃烧指南】 一、基础概念 1. API网关&#xff08;API Gateway&#xff09; API网关是微服务架构中的核心组件&#xff0c;负责统一管理所有API的流量入口。它像一座…...

RSS 2025|从说明书学习复杂机器人操作任务:NUS邵林团队提出全新机器人装配技能学习框架Manual2Skill

视觉语言模型&#xff08;Vision-Language Models, VLMs&#xff09;&#xff0c;为真实环境中的机器人操作任务提供了极具潜力的解决方案。 尽管 VLMs 取得了显著进展&#xff0c;机器人仍难以胜任复杂的长时程任务&#xff08;如家具装配&#xff09;&#xff0c;主要受限于人…...