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

LeetCode-前缀和-和为K的子数组

news 来源：原创 2025/7/16 21:47:05

618224d51d66b92b423588150f25f3a7-1746706818078-1-1746790482186-1-1746797747208-4

LeetCode-前缀和-和为K的子数组

✏️ 关于专栏：专栏用于记录 prepare for the coding test。

文章目录

LeetCode-前缀和-和为K的子数组
- 📝 和为K的子数组
- - 🎯题目描述
  - 🔍 输入输出示例
  - 🧩题目提示
  - 🧪前缀和
  - - ❓什么是“前缀和”？
    - 🤔 如何用前缀和优化“和为 k 的子数组”问题？
  - 🌟 总结
  - - 🔚回顾前缀和知识整理（含差分）
    - - ✅ 一维前缀和
      - ✅ 一维差分（前缀和的逆运算）
      - ✅ 二维前缀和
      - ✅ 二维差分

📝 和为K的子数组

🎯题目描述

给你一个整数数组 nums 和一个整数 k ，请你统计并返回 该数组中和为 k 的子数组的个数 。

子数组是数组中元素的连续非空序列。

🔗题目链接：和为K的子数组

🔍 输入输出示例

示例 1:

输入：nums = [1,1,1], k = 2
输出：2

示例 2:

输入：nums = [1,2,3], k = 3
输出：2

🧩题目提示

1 <= nums.length <= 2 * 104
-1000 <= nums[i] <= 1000
-107 <= k <= 107

🧪前缀和

❓什么是“前缀和”？

前缀和是一个技巧，用于快速计算数组任意一段区间 [i, j] 的和。

我们构造一个辅助数组 s，令：

s[i] 表示 nums[0] + nums[1] + ... + nums[i-1]

那么区间和 nums[i..j] 就可以表示为：

s[j+1] - s[i]

🤔 如何用前缀和优化“和为 k 的子数组”问题？

关键点在于变换等式：

s[j+1] - s[i] == k  ⟺  s[i] == s[j+1] - k

换句话说，每次计算一个新的前缀和 s[j+1]，我们就可以检查之前有多少个前缀和等于 s[j+1] - k，那么这些位置开始的子数组就是合法的。

这个过程使用一个 unordered_map<int, int> 来实时记录每个前缀和的出现次数（频次），可以在 O(1) 时间内查询和更新。

class Solution {
public:int subarraySum(vector<int>& nums, int k) {int n = nums.size();vector<int> s(n + 1);for(int i = 0;i < n;i++){s[i + 1] = s[i] + nums[i];}int ans = 0;unordered_map<int,int> cnt;for(int i = 0;i < s.size();i++){ans += cnt.contains(s[i] - k) ? cnt[s[i] - k] : 0;cnt[s[i]]++;}return ans;}
};

🌟 总结

前缀和（Prefix Sum） 是一种常见的预处理技巧，主要用于在 O(1) 时间内求任意子数组/区间的连续和。

前缀和本质是对数组进行一次扫描，将每个位置之前的累积值保存下来，方便后续快速计算区间和。

设原数组为 nums，构建前缀和数组 prefix（或 s），定义如下：

prefix[0] = 0
prefix[i] = nums[0] + nums[1] + ... + nums[i - 1]

那么任意一个区间 [i, j] 的子数组和为：

sum(i..j) = prefix[j + 1] - prefix[i]

前缀和 = “先累加、后查找”，是快速处理连续区间求和问题的利器，尤其适用于带有“连续”、“区间”、“子数组”、“和为 K”、“模 K”等关键词的问题。

使用前缀和 + 哈希表可以高效统计和为 k 的子数组个数；
关键是理解：s[j+1] - s[i] == k => s[i] = s[j+1] - k
初始化 cnt[0] = 1 是处理从头开始的子数组的必要手段。

🔚回顾前缀和知识整理（含差分）

✅ 一维前缀和

定义：
给定数组 a[1..n]，定义前缀和数组 s[i] = a[1] + a[2] + ... + a[i]
其中 s[0] = 0

求区间和 [l, r]：

int sum = s[r] - s[l - 1];

构建代码：

for (int i = 1; i <= n; i++) {s[i] = s[i - 1] + a[i];
}

✅ 一维差分（前缀和的逆运算）

定义：
差分数组 d[i] = a[i] - a[i - 1]，可用于快速区间修改

区间加法操作：对区间 [l, r] 加 x

d[l] += x;
d[r + 1] -= x;

最终恢复原数组 a：

a[1] = d[1];
for (int i = 2; i <= n; i++) {a[i] = a[i - 1] + d[i];
}

✅ 二维前缀和

定义：
给定二维数组 a[i][j]，定义二维前缀和 s[i][j] = a[1][1] + ... + a[i][j]

构建公式：

s[i][j] = s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1] + a[i][j];

求子矩阵和 [(x1,y1), (x2,y2)]：

int sum = s[x2][y2] - s[x1 - 1][y2] - s[x2][y1 - 1] + s[x1 - 1][y1 - 1];

✅ 二维差分

定义：
d[i][j] = a[i][j] - a[i-1][j] - a[i][j-1] + a[i-1][j-1]

对子矩阵 [(x1,y1), (x2,y2)] 加 x：

d[x1][y1] += x;
d[x2+1][y1] -= x;
d[x1][y2+1] -= x;
d[x2+1][y2+1] += x;

恢复原数组：

for (int i = 1; i <= n; i++)for (int j = 1; j <= m; j++)a[i][j] = a[i - 1][j] + a[i][j - 1] - a[i - 1][j - 1] + d[i][j];

📌应用场景：

一维前缀和：快速求区间和
一维差分：快速区间加减
二维前缀和：求子矩阵和
二维差分：矩阵局部批量修改

473a45227a39b7ec06f6525e7ebb85b

LeetCode-前缀和-和为K的子数组

LeetCode-前缀和-和为K的子数组 ✏️ 关于专栏：专栏用于记录 prepare for the coding test。文章目录 LeetCode-前缀和-和为K的子数组📝 和为K的子数组🎯题目描述🔍 输入输出示例🧩题目提示🧪前缀和❓什么…...

编程日记 2025/7/16 21:47:05

MySQL基础关键_014_MySQL 练习题

目录一、有以下表，请用一条 SQL 语句查询出每门课程都大于 80 分的学生二、综合题1（数据自行模拟） 1.查询身份证号为“440401430103082”的申请日期 2.查询同一个身份证号有两条及以上记录的身份证号码及记录个数 3.将身份证号码为“4…...

编程日记 2025/7/14 10:51:19

femap许可与云计算集成

随着云计算技术的迅猛发展，越来越多的企业开始将关键应用和服务迁移到云端，以享受其带来的弹性扩展、高效管理和成本优化等优势。Femap作为一款强大的电磁仿真工具，通过与云计算的集成，将为企业带来前所未有的许可管理和仿真分析体…...

编程日记 2025/6/28 22:01:59

uni-app项目从0-1基础架构搭建全流程

前情最近新接了一个全新项目，我负责从0开始搭建小程序，我选用的技术栈是uni-app技术栈，UI库选择的是uview-plus，CSS引入现在流行的tainlwindcss，实现CSS原子化书写，实现小程序分包，分包中实现…...

编程日记 2025/7/10 10:37:29

轻量级高性能推理引擎MNN 学习笔记 04.线性回归

1. 线性回归 MNN 官方给的iOS Demo中，输入是图片，输出是分类结果，相对来讲，略微有些复杂，我们现在用一个最简单的线性回归模型，来说明MNN的用法。该线性回归是yaxb （其中a2,b0.01&#xff09…...

编程日记 2025/7/12 22:44:42

使用 React PDF 构建 React.js PDF 查看器的指南

在本文中，我们将重点介绍在React.js中制作 PDF 查看器的最受欢迎的开源库。具体来说，我们将利用著名的开源库react-pdf的功能，指导您完成创建 React.js PDF 查看器的过程。通过本教程，您将在第一部分学习如何使用 React-PDF 在 …...

编程日记 2025/7/12 16:48:09

动力电池点焊机厂家：驱动新能源制造的精密力量|比斯特自动化

在新能源汽车、储能系统等产业蓬勃发展的背景下，动力电池点焊机作为电池模组生产的核心设备，正经历着技术迭代与市场需求的双重升级。这类厂家通过持续研发与创新，不仅满足了电池制造企业对焊接精度、效率与稳定性的严苛要求，更推…...

编程日记 2025/7/11 5:04:12

React的合成事件（SyntheticEventt）

文章目录前言前言 React的合成事件（SyntheticEvent）是React为了统一不同浏览器的事件处理行为而封装的一套跨浏览器事件系统。它与原生事件的主要区别如下： 1. 事件绑定方式 • 合成事件：使用驼峰命名法绑定事件（如…...

编程日记 2025/7/16 16:37:40

知识中台Top5：Baklib上榜推荐

Baklib知识中台优势在数字化转型浪潮中，Baklib凭借其知识中台的核心设计理念，构建了企业级知识管理的差异化竞争力。区别于传统文档管理系统，该平台通过四库体系（知识资源库、场景规则库、服务模型库、应用组件库）实…...

编程日记 2025/7/14 11:55:44

在Windows系统中使用C++与Orthanc交互：基于DICOMweb的医学影像应用开发

🧑 博主简介：CSDN博客专家、CSDN平台优质创作者，高级开发工程师，数学专业，10年以上C/C, C#, Java等多种编程语言开发经验，拥有高级工程师证书；擅长C/C、C#等开发语言，熟悉Java常用开…...

编程日记 2025/7/10 17:00:48

视频太大？用魔影工厂压缩并转MP4，画质不打折！

在日常生活中，我们常常需要将视频文件转换成不同的格式以适应各种设备或平台的播放需求。魔影工厂作为一款功能强大且操作简单的视频转换工具，深受用户喜爱。本文中简鹿办公将手把手教你如何使用魔影工厂将视频转换为MP4格式，并进行个性化设置…...

编程日记 2025/7/1 21:51:14

Wan2.1 通过首尾帧生成视频

Wan2.1 通过首尾帧生成视频 flyfish 使用 Wan2.1-FLF2V-14B-720P 模型，通过输入两张图像（起始帧和结束帧），生成一段连贯的视频。 First Last Frame-to-Video 即 “首末帧到视频” 技术 import numpy as np import torch import…...

编程日记 2025/7/16 10:58:43

宝塔+fastadmin：给项目添加定时任务

一、定时任务脚本编写 1. 使用 shebang 声明执行器 #!/usr/bin/env php 这是 Unix/Linux 系统中脚本文件的标准开头。表示这个脚本使用系统环境变量中的 php 来执行。2. 定义 ThinkPHP 入口路径并加载框架 define(APP_PATH, __DIR__ . /../../application/); require __DIR__…...

编程日记 2025/7/16 7:38:30

[自动化集成] 使用明道云上传附件并在Python后端处理Excel的完整流程

在企业日常自动化场景中，使用低代码平台如明道云搭建前端界面，结合自定义Python后端服务，实现灵活数据处理是一种高效的组合方式。本文将分享一个典型的集成用例：用户通过明道云上传文本和Excel附件，Python后端接收并解析这些信息，最终实现完整的数据处理闭环。项目背景…...

编程日记 2025/7/14 0:14:57

前端项目采用响式布局

要让整个前端项目采用响应式布局，可以从多个方面进行优化，以下是一些具体的建议和实现方法： 1. 使用 ElementPlus 的响应式特性 ElementPlus 组件库本身提供了一些响应式的能力，例如 el-col 组件可以用于创建响应式的网格布局。…...

编程日记 2025/7/7 22:39:19

【Unity】DOTween的常用函数解释

DOTween插件常用函数解释 1.DOTween.To（通用变化动画） 解释：将某一个值在一定的时间内变化到另一个值（通用的函数），可用于大部分的动画变化使用示例： using UnityEngine; using DG.Tweenin…...

编程日记 2025/7/11 1:12:24

飞桨paddle import fluid报错【已解决】

跟着飞桨的安装指南安装了paddle之后 pip install paddlepaddle有一个验证： import paddle.fluid as fluid fluid.install check.run check()报错情况如下，但是我在pip list中，确实看到了paddle安装上了我import paddle别的包&#xff0c…...

编程日记 2025/7/10 1:18:59

ELK简介和docker版安装

使用场景主要还是给开发人员“打捞日志”用的。 ELK 是由三个开源工具组成的套件（Elasticsearch、Logstash 和 Kibana），主要用于日志的收集、分析和可视化。以下是 ELK 常见的使用场景： 日志集中化管理收集来自多个服务器或服…...

编程日记 2025/7/10 5:05:52

DockerHub被封禁，怎么将镜像传到国内？一种简单合规的镜像同步到国内方案[最佳实践]

Docker将容器化技术普及，推动云计算向云原生的演进。Docker的核心创新技术之一是容器镜像，它是一种文件的打包方式，将应用程序运行的操作系统、库、运行环境等依赖全部打包一起。在其他任意环境，只要可以运行docker服务&#xff0…...

编程日记 2025/7/16 21:41:24

飞桨paddle ‘ParallelEnv‘ object has no attribute ‘_device_id‘【已解决】

书借上回，自从我反复重装paddle之后，我发现了，只要pip list中有库，但是代码报错，那就是飞桨没把代码更新完全，只能自己去改源代码我又遇到报错了： 根据报错信息，找到ParallelEnv报…...

编程日记 2025/7/2 3:53:11

网络安全面试题（一）

文章目录一、基础概念与模型‌1. 什么是通信协议？列举三种常见的网络通信模型？2. 解释OSI七层模型及各层功能3. TCP/IP四层模型与OSI模型的对应关系是什么？4. 五层协议体系结构与TCP/IP模型的区别?5. 什么是面向连接与非面向连接的服务&…...

编程日记 2025/7/16 12:17:55

问题背景给定一个长度为 n n n 的整数数组 n u m s nums nums 和一个二维数组 q u e r i e s queries queries，其中 q u e r i e s [ i ] [ l i , r i ] queries[i] [l_i, r_i] queries[i][li,ri]。对于每个查询 q u e r i e s [ i ] queries[i] quer…...

编程日记 2025/7/6 14:21:21

RK3588 ArmNN CPU/GPU ResNet50 FP32/FP16/INT8 推理测试

RK3588 ArmNN CPU/GPU ResNet50 FP32/FP16/INT8 推理测试 **背景与目标** 一.性能数据【INT8模型在CPU上推理的结果已经不对,暂未分析原因】二.操作步骤2.1 在x86-Linux上生成onnx模型,以及tflite量化模型(避免在RK3588上安装过多依赖)2.1.1 创建容器2.1.2 安装依赖2.1.3 下载推…...

编程日记 2025/7/16 21:42:29

力扣第5题：最长回文子串（动态规划）

小学生一枚，自学信奥中，没参加培训机构，所以命名不规范、代码不优美是在所难免的，欢迎指正。标签： 字符串、动态规划、中心扩散法语言： C 题目： 给你一个字符串s，找到s中最长的…...

编程日记 2025/7/16 1:42:44

HCIP实验五

一、实验拓扑图： 二、实验需求分析： 1. PreVal策略：要求确保R4通过R2到达192.168.10.0/24 ，需在R4上针对去往该网段路由配置PreVal策略，为经R2的路径赋予更高优先值，影响本地路由表选路。 2. AS Path策略…...

编程日记 2025/7/15 4:59:06

python Numpy-数组

目录 Numpy： 一、Ndarray 1 定义 2 数组的属性方法 2.1 数组的维度：np.ndarray.shape 2.2 元素的类型：np.ndarray.dtype 2.3 数组元素的个数：np.ndarray.size 2.4 转置 3 ndarray 所存储元素的数据类型 4 数组创建 4.1 a…...

编程日记 2025/7/16 16:28:06

数据库分库分表从理论到实战

1.分库分表基础理论 1.1 分库分表基本概念定义：分库分表是一种将单一数据库中的数据分散存储到多个数据库或表中的技术方案，其核心思想是通过"分而治之"的方式解决数据库性能瓶颈问题。分库：将表按业务或数据量拆分到不同数据库中…...

编程日记 2025/7/15 17:19:32

Java异常处理与File类终极指南

Java异常处理与File类终极指南目录异常体系全维度拆解异常处理十五种高阶模式自定义异常企业级实践File类深度探索与NIO进化论分布式系统异常处理架构性能调优与安全防护全网最全异常代码库一、异常体系全维度拆解 1.1 Java异常DNA解析 // 异常类的核心继承关系 public cla…...

编程日记 2025/7/10 13:26:51

pmap中的mode列，脏页，写时复制

写时复制（Copy-on-Write，简称 COW） 是一种计算机编程中的优化技术，主要用于内存或存储资源的管理。其核心思想是：只有在真正需要修改数据时，才会执行实际的复制操作，从而避免不必要的资源开销。…...

编程日记 2025/7/15 4:48:19

通过COM获取正在运行的Excel实例并关闭 c#实现

利用COM对象模型获取正在运行的Excel实例并关闭。示例代码如下： using Excel Microsoft.Office.Interop.Excel; using System.Runtime.InteropServices; try { Excel.Application excelApp (Excel.Application)Marshal.GetActiveObject("Excel.Applicatio…...

编程日记 2025/7/16 8:35:13

运行在华为云kubernetes应用接入APM服务

1 APM概述在云时代微服务架构下应用日益丰富，纷杂的应用异常问题接踵而来。应用运维面临巨大挑战： 分布式应用关系错综复杂，应用性能问题分析定位困难，应用运维面临如何保障应用正常、快速完成问题定位、迅速找到性能瓶颈的挑战…...

编程日记 2025/7/2 10:56:54

虚幻引擎5-Unreal Engine笔记之摄像头camera

虚幻引擎5-Unreal Engine笔记之摄像头camera code review! 目录第一部分：摄像头的基础概念 1.1 UE5 中摄像头的定义与作用1.2 UE5 中摄像头的类型与分类第二部分：摄像头的代码结构与分类 2.1 摄像头是类还是组件？2.2 组件的本质&#xff…...

编程日记 2025/7/2 17:59:29

mysql的基础命令

1.SQL的基本概念 SQL 是用于管理和操作关系型数据库的标准编程语言。是所有关系型数据库（如 MySQL、PostgreSQL、Oracle 等）的通用语言。 SQL语句分类 DDL: Data Defination Language 数据定义语言 CREATE，DROP，ALTER DML: Da…...

编程日记 2025/7/13 1:33:54

去中心化算力池：基于IPFS+智能合约的跨校GPU资源共享平台设计

点击 “AladdinEdu，同学们用得起的【H卡】算力平台”，H卡级别算力，按量计费，灵活弹性，顶级配置，学生专属优惠。一、问题背景：高校算力孤岛的困境现状痛点各高校GPU集群利用率差异显著&…...

编程日记 2025/7/15 5:14:42

数据库（二）：ORM技术

什么是 ORM？ ORM（Object-Relational Mapping） 是一种用于实现对象模型（面向对象）与关系模型（数据库）之间映射的技术，使程序员可以通过操作对象的方式访问数据库数据，而无…...

编程日记 2025/7/15 11:16:08

Oracle基础知识

目录 1.别名的使用 2.AND的优先级高于OR 3.where后面可以接别名，order by后面不可以 4.Oracle中SQL的执行顺序(重点) 5.dual万用表 6.是否区分大小写 7.Oracle常用数据类型 8.Oracle常用函数 (1)length字符、lengthb字节和cast强制类型转换 (2)数据类型转…...

编程日记 2025/7/9 1:16:26

使用 vite-plugin-dynamic-base 实现运行时动态设置上下文路径

我们一般会在编译之前设置上下文，那么如何在编译之后动态设置上下文的路径？ 本文使用的技术栈是 Go（Gin） Vue.js（Vite） 本文使用到的第三方包：https://github.com/chenxch/vite-plugin-dynam…...

编程日记 2025/7/16 6:40:06

spark-shuffle 类型及其对比

1. Hash Shuffle 原理：将数据按照分区键进行哈希计算，将相同哈希值的数据发送到同一个Reducer中。特点：实现简单，适用于数据分布均匀的场景。但在数据分布不均匀时，容易导致某些Reducer处理的数据量过大，产…...

编程日记 2025/7/10 14:46:36

力扣-快乐数

1.题目要求 2.题目链接 202. 快乐数 - 力扣（LeetCode） 3.题目分析首先,因为需要频繁地用到数字变为各个位上的平方的过程,我们可以将"对于一个正整数,每一次将该数替换为它每个位置的数字的平方和"这一操作抽象出来，定义成一个…...

编程日记 2025/7/16 5:34:36

每日算法刷题Day10 5.19:leetcode不定长滑动窗口求最长/最大4道题，结束定长滑动窗口,用时1h

不定长滑动窗口不定长滑动窗口主要分为三类：求最长子数组，求最短子数组，以及求子数组个数。注：滑动窗口相当于在维护一个队列。右指针的移动可以视作入队，左指针的移动可以视作出队。滑动窗口【基础算法精讲 03】…...

编程日记 2025/7/11 23:30:28

FreeSWITCH 纯内网配置

纯内网，且同一个网段，Fs 可简化配置，要点是: 1. 不需要事先配置 directory，任意号码都可以注册，且无挑战 2. 呼叫无挑战不需要考虑那么多安全问题配置如下： 1. 全局变量 <X-PRE-PROCESS cmd"…...

编程日记 2025/7/13 8:53:22

STL中list的模拟

这里写目录标题 list 的节点 —— ListNodelist 的 “导览员” —— ListIteratorlist 的核心 —— list 类构造函数迭代器相关操作容量相关操作结尾在 C 的 STL（标准模板库）中，list 是一个十分重要的容器，它就像一个灵活的弹簧…...

编程日记 2025/7/16 17:40:02

【iOS】类结构分析

前言之前我们已经探索得出对象的本质就是一个带有isa指针的结构体，这篇文章来分析一下类的结构以及类的底层原理。类的本质类的本质我们在main函数中写入以上代码，然后利用clang对其进行反编译，可以得到c文件可以看到底层使用Class接…...

编程日记 2025/7/8 8:07:34

Android 万能AI证件照 v1.3.2

在日常的生活和工作场景里，证件照的身影随处可见。找工作投简历时，它是展现你形象的 “第一张名片”；办理各类证件，缺了它可不行；参加各种考试报名，同样需要它。可以说，证件照虽小，却…...

编程日记 2025/7/16 10:21:34

【Java】封装在 Java 中是怎样实现的?

包关于包有两个关键字 package : 声明当前类属于哪个包和 import : 允许当前类使用其他类或接口时不使用全限定名 , 也就是导包 . IDEA 的普通项目文件包括 src : 包含源码和资源文件和 out : 包含编译产物字节码文件 . 在 IDEA 开发环境建包会在 src 源码目录中生成 , 可…...

编程日记 2025/7/15 19:36:05