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

conda相比python好处

Conda 作为 Python 的环境和包管理工具&#xff0c;相比原生 Python 生态&#xff08;如 pip 虚拟环境&#xff09;有许多独特优势&#xff0c;尤其在多项目管理、依赖处理和跨平台兼容性等方面表现更优。以下是 Conda 的核心好处&#xff1a; 一、一站式环境管理&#xff1a…...

TDengine 快速体验(Docker 镜像方式)

简介 TDengine 可以通过安装包、Docker 镜像 及云服务快速体验 TDengine 的功能&#xff0c;本节首先介绍如何通过 Docker 快速体验 TDengine&#xff0c;然后介绍如何在 Docker 环境下体验 TDengine 的写入和查询功能。如果你不熟悉 Docker&#xff0c;请使用 安装包的方式快…...

AI Agent与Agentic AI:原理、应用、挑战与未来展望

文章目录 一、引言二、AI Agent与Agentic AI的兴起2.1 技术契机与生态成熟2.2 Agent的定义与特征2.3 Agent的发展历程 三、AI Agent的核心技术栈解密3.1 感知模块代码示例&#xff1a;使用Python和OpenCV进行图像识别 3.2 认知与决策模块代码示例&#xff1a;使用OpenAI GPT-3进…...

ssc377d修改flash分区大小

1、flash的分区默认分配16M、 / # df -h Filesystem Size Used Available Use% Mounted on /dev/root 1.9M 1.9M 0 100% / /dev/mtdblock4 3.0M...

基于Uniapp开发HarmonyOS 5.0旅游应用技术实践

一、技术选型背景 1.跨平台优势 Uniapp采用Vue.js框架&#xff0c;支持"一次开发&#xff0c;多端部署"&#xff0c;可同步生成HarmonyOS、iOS、Android等多平台应用。 2.鸿蒙特性融合 HarmonyOS 5.0的分布式能力与原子化服务&#xff0c;为旅游应用带来&#xf…...

C++ 基础特性深度解析

目录 引言 一、命名空间&#xff08;namespace&#xff09; C 中的命名空间​ 与 C 语言的对比​ 二、缺省参数​ C 中的缺省参数​ 与 C 语言的对比​ 三、引用&#xff08;reference&#xff09;​ C 中的引用​ 与 C 语言的对比​ 四、inline&#xff08;内联函数…...

视频字幕质量评估的大规模细粒度基准

大家读完觉得有帮助记得关注和点赞&#xff01;&#xff01;&#xff01; 摘要 视频字幕在文本到视频生成任务中起着至关重要的作用&#xff0c;因为它们的质量直接影响所生成视频的语义连贯性和视觉保真度。尽管大型视觉-语言模型&#xff08;VLMs&#xff09;在字幕生成方面…...

SpringBoot+uniapp 的 Champion 俱乐部微信小程序设计与实现,论文初版实现

摘要 本论文旨在设计并实现基于 SpringBoot 和 uniapp 的 Champion 俱乐部微信小程序&#xff0c;以满足俱乐部线上活动推广、会员管理、社交互动等需求。通过 SpringBoot 搭建后端服务&#xff0c;提供稳定高效的数据处理与业务逻辑支持&#xff1b;利用 uniapp 实现跨平台前…...

聊一聊接口测试的意义有哪些?

目录 一、隔离性 & 早期测试 二、保障系统集成质量 三、验证业务逻辑的核心层 四、提升测试效率与覆盖度 五、系统稳定性的守护者 六、驱动团队协作与契约管理 七、性能与扩展性的前置评估 八、持续交付的核心支撑 接口测试的意义可以从四个维度展开&#xff0c;首…...

tree 树组件大数据卡顿问题优化

问题背景 项目中有用到树组件用来做文件目录&#xff0c;但是由于这个树组件的节点越来越多&#xff0c;导致页面在滚动这个树组件的时候浏览器就很容易卡死。这种问题基本上都是因为dom节点太多&#xff0c;导致的浏览器卡顿&#xff0c;这里很明显就需要用到虚拟列表的技术&…...