[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,你需要找到该数组中和为 k 的连续的子数组的个数。示例 1 :输入:nums [1,1,1], k 2 输出: 2 , [1,1] 与 [1,1] 为两种不同的情况。 说明 :数组的长度为 [1, 20,000]。 数组中元素的范围是 [-1000, 1000] ,且整…...
Leo赠书活动-02期 【信息科技风险管理:合规管理、技术防控与数字化】
✅作者简介:大家好,我是Leo,热爱Java后端开发者,一个想要与大家共同进步的男人😉😉 🍎个人主页:Leo的博客 💞当前专栏: 赠书活动专栏 ✨特色专栏:…...
L2-026 小字辈 - java
L2-026 小字辈 时间限制 400 ms 内存限制 64 MB 题目描述: 本题给定一个庞大家族的家谱,要请你给出最小一辈的名单。 输入格式: 输入在第一行给出家族人口总数 N(不超过 100 000 的正整数) —— 简单起见,…...
排序算法-堆积树排序法(HeapSort)
目录 排序算法-堆积树排序法(HeapSort) 1、说明 2、算法分析 3、C代码 排序算法-堆积树排序法(HeapSort) 1、说明 堆积树排序法是选择排序法的改进版,可以减少在选择排序法中的比较次数,进而减少排序…...
名词解释 MongoDB
MongoDB 是一个面向文档的数据库管理系统,它不使用传统的表格结构,而是将数据组织成类似文档的形式,通常使用JSON格式。 文档数据库:数据以文档的形式存储,每个文档可以包含不同的字段,就像一个文件可以包…...
Look Back(cf div3 905)
题意:给你一个长度为n((1≤n≤10^5)数组a[],你可以进行一个操作 使a[i]a[i]*2,问最少经过多少次这样的操作使的a[]不递减,a[i]>a[i-1]。 输入样例: 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年以来,Spring框架已经成为Java开发人员最受欢迎的开源框架之一。它提供了一个全面的编程和配置模型,旨在简化企业级Java应用程序的开发过程。本文将详细介绍Spring框架的发展历程,以及它如何为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的版本
本章内容包括: Excel与Power BI的比较选择Power BI的桌面版和服务版之间的差异了解Microsoft提供的许可选项 挑选正确版本的Power BI可能就像参观世界上最大的糖果店:你可以从许多细微差别的替代品中进行选择。选择可以归结为想要、需要、规模…...
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,R1,调用C函数时,第一个参数保存在R0中第二个参数保存在R1中。这是约定。 指令保存在哪里? 指令保存在flash上面 LR等于什么? LR是返回地址,函数执行完了过后LR等于下一条指令的地址 运行…...
python 桌面软件开发-matplotlib画图鼠标缩放拖动
继上一篇在 Java 中缩放拖动图片后,在python matplotlib中也来实现一个自由缩放拖动的例子: python matplotlib 中缩放,较为简单,只需要通过设置要显示的 x y坐标的显示范围即可。基于此,实现一个鼠标监听回调…...
【JavaScript基础】JavaScript头等函数的理解
彻底理解JavaScript头等函数 一、函数的理解 🔥 什么是函数? 一般来说,一个函数是可以通过外部代码 调用 的一个“子程序”(或在递归的情况下由内部函数调用)。像程序本身一样,一个函数由称为函数体的一…...
如何把项目上传到Gitee(详细教程)
找到项目根目录右键打开Git Bash Here 输入命令:git init 回车 输入命令:git status 输入命令:git add . 输入命令:git status git commit -m 项目描述 在Gitee官网注册好账号后,git 新建项目 填写补充git项目信息及…...
Ubuntu挂载windows下的共享文件夹
Ubuntu挂载windows下的共享文件夹 更新apt源 如果出现安装失败,需要更新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系统是一种用于仓库管理的信息化系统,旨在提高仓库操作的效率和准确性。而在WMS系统中,条码化管理是一项关键的技术和方法,它通过将商品和物料打上条码,并利用扫描设备进行数据采集和处理,实现了仓库管理的全面自动…...
【云原生之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 (窗口/分区函数)
🧲相关文章 [1] MySQL 系统表解析以及各项指标查询 [2] MySQL 5.7 JSON 字段的使用的处理 [3] MySQL经典练习50题 简介 MySQL 8.0版本开始支持窗口函数 官方文档 在之前的版本中已存在的大部分聚合函数,在MySQL 8 中也可以作为窗口函数来使用 方法 / …...
openGauss Meetup(天津站)精彩回顾 | openGauss天津用户组正式成立
由openGauss社区、天开发展集团、天津市软件行业协会、天大智图(天津)科技有限公司联合主办的“openGauss Meetup • 天津站”已于10月13日落下帷幕,此次活动邀请到众多业内技术专家,从技术创新、学术创新、发展创新、以及生态共建…...
深入浅出Asp.Net Core MVC应用开发系列-AspNetCore中的日志记录
ASP.NET Core 是一个跨平台的开源框架,用于在 Windows、macOS 或 Linux 上生成基于云的新式 Web 应用。 ASP.NET Core 中的日志记录 .NET 通过 ILogger API 支持高性能结构化日志记录,以帮助监视应用程序行为和诊断问题。 可以通过配置不同的记录提供程…...
【kafka】Golang实现分布式Masscan任务调度系统
要求: 输出两个程序,一个命令行程序(命令行参数用flag)和一个服务端程序。 命令行程序支持通过命令行参数配置下发IP或IP段、端口、扫描带宽,然后将消息推送到kafka里面。 服务端程序: 从kafka消费者接收…...
智慧医疗能源事业线深度画像分析(上)
引言 医疗行业作为现代社会的关键基础设施,其能源消耗与环境影响正日益受到关注。随着全球"双碳"目标的推进和可持续发展理念的深入,智慧医疗能源事业线应运而生,致力于通过创新技术与管理方案,重构医疗领域的能源使用模式。这一事业线融合了能源管理、可持续发…...
【机器视觉】单目测距——运动结构恢复
ps:图是随便找的,为了凑个封面 前言 在前面对光流法进行进一步改进,希望将2D光流推广至3D场景流时,发现2D转3D过程中存在尺度歧义问题,需要补全摄像头拍摄图像中缺失的深度信息,否则解空间不收敛…...
聊一聊接口测试的意义有哪些?
目录 一、隔离性 & 早期测试 二、保障系统集成质量 三、验证业务逻辑的核心层 四、提升测试效率与覆盖度 五、系统稳定性的守护者 六、驱动团队协作与契约管理 七、性能与扩展性的前置评估 八、持续交付的核心支撑 接口测试的意义可以从四个维度展开,首…...
【生成模型】视频生成论文调研
工作清单 上游应用方向:控制、速度、时长、高动态、多主体驱动 类型工作基础模型WAN / WAN-VACE / HunyuanVideo控制条件轨迹控制ATI~镜头控制ReCamMaster~多主体驱动Phantom~音频驱动Let Them Talk: Audio-Driven Multi-Person Conversational Video Generation速…...
嵌入式学习笔记DAY33(网络编程——TCP)
一、网络架构 C/S (client/server 客户端/服务器):由客户端和服务器端两个部分组成。客户端通常是用户使用的应用程序,负责提供用户界面和交互逻辑 ,接收用户输入,向服务器发送请求,并展示服务…...
【笔记】WSL 中 Rust 安装与测试完整记录
#工作记录 WSL 中 Rust 安装与测试完整记录 1. 运行环境 系统:Ubuntu 24.04 LTS (WSL2)架构:x86_64 (GNU/Linux)Rust 版本:rustc 1.87.0 (2025-05-09)Cargo 版本:cargo 1.87.0 (2025-05-06) 2. 安装 Rust 2.1 使用 Rust 官方安…...
mac 安装homebrew (nvm 及git)
mac 安装nvm 及git 万恶之源 mac 安装这些东西离不开Xcode。及homebrew 一、先说安装git步骤 通用: 方法一:使用 Homebrew 安装 Git(推荐) 步骤如下:打开终端(Terminal.app) 1.安装 Homebrew…...
Linux nano命令的基本使用
参考资料 GNU nanoを使いこなすnano基础 目录 一. 简介二. 文件打开2.1 普通方式打开文件2.2 只读方式打开文件 三. 文件查看3.1 打开文件时,显示行号3.2 翻页查看 四. 文件编辑4.1 Ctrl K 复制 和 Ctrl U 粘贴4.2 Alt/Esc U 撤回 五. 文件保存与退出5.1 Ctrl …...
