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

[Leetcode] 560 Subarray Sum Equals K

题意:给定一个数组求连续的子数组的和为k的有几个
Input: nums = [1,1,1], k = 2
Output: 2

https://leetcode.com/problems/subarray-sum-equals-k/description/

首先思考1.因为是subarray sum前缀和很容易想到,那问题就转化成preSum[i] = preSum[j] - k (i < j)求个数的问题,那么hashmap就很容易想到了
思考2: dp,但是dp在这里有个问题,1维dp是没有办法解决这个问题的,这种类型的dp一般是dp[i],意思是以右端点为i的subarray sum,但是dp[i]找不到任何可以递推的等式,所以必须引入左端点做二维dp,那么问题的复杂度就高了
还有一个点是,第二个for循环中,必须要引入preSum[0], 因为preSum[i] - preSum[0]是0-i的数字全包括的情况

class Solution {
public:int subarraySum(vector<int>& nums, int k) {//preSum[j] - preSum[i] = k//preSum[i] = preSum[j] - k (i < j)int m = nums.size();vector<int> preSum(m+1, 0);preSum[0] = 0;for(int i = 1; i < preSum.size(); i++) {preSum[i] = preSum[i-1] + nums[i-1]; }int ret = 0;unordered_map<int, int> mp;for(int i = 0; i < preSum.size(); i++) {if(mp.count(preSum[i]-k) > 0) {ret += mp[preSum[i]-k];}mp[preSum[i]]++;}return ret;}
};

时间O(n), 空间O(n)

相关文章:

[Leetcode] 560 Subarray Sum Equals K

题意&#xff1a;给定一个数组求连续的子数组的和为k的有几个 Input: nums [1,1,1], k 2 Output: 2 https://leetcode.com/problems/subarray-sum-equals-k/description/ 首先思考1.因为是subarray sum前缀和很容易想到&#xff0c;那问题就转化成preSum[i] preSum[j] - k…...

TCL Android面试题大全及参考答案

能谈谈Jetpack组件吗? Jetpack 是一套用于 Android 开发的工具和组件库,它可以帮助开发者更高效地构建高质量的 Android 应用。 一、主要组件分类 架构组件: ViewModel:负责存储和管理与界面相关的数据,当屏幕旋转或配置发生变化时,ViewModel 可以帮助保存数据,避免数据…...

JVM错误:OutOfMemoryError: GC overhead limit exceeded

OutOfMemoryError: GC overhead limit exceeded 在Window服务器上跑一个项目&#xff0c;无意中出现服务访问不了&#xff0c;查看日志文档&#xff0c;第一次遇到了这个异常信息。 1. 错误含义 OutOfMemoryError: GC overhead limit exceeded 是 JVM 中的一种错误&#xff…...

Unity网络开发 - C#开源网络通信库PESocket的使用

概述 在现代多人在线游戏中&#xff0c;稳定且高效的网络通信是确保游戏体验的关键。本文将探讨如何利用C#开源网络通信库PESocket来构建一个简单的Unity客户端与.NET控制台服务器之间的实时消息传递系统。通过本例&#xff0c;读者不仅能够了解PESocket的基本用法&#xff0c…...

【完-网络安全】Shell与脚本

文章目录 1.CLI与GUI2.终端和Shell2.1 Shell 壳层2.2 终端2.3 终端和Shell区别3.标准流 4.PowerShell4.1 管理员与非管理员4.2 指令4.3 重定向4.4 管道 5.环境变量5.1 影响范围5.2环境变量的作用5.3 常见的环境变量 6.脚本 1.CLI与GUI CLI命令行界面(CLl,Command Line Interfa…...

磁盘标签和分区标签

在Windows中&#xff0c;我们为分区命名&#xff0c;那个名字就是「分区标签」。所以说“分区标签”是给分区的一个名字。 「磁盘标签」其实是我们经常说的「分区表」&#xff0c;比如MBR、GPT等等。而「分区标签」&#xff0c;虽然叫做“分区”标签&#xff0c;但它则是文件系…...

关于摩托车一键启动无钥匙进入、智能科技创新

摩托车一键启动无钥匙进入功能 一、工作原理 摩托车的一键启动无钥匙进入功能采用了世界最先进的RFID无线射频技术和最先进的车辆身份编码识别系统&#xff0c;率先应用小型化、小功率射频天线的开发方案&#xff0c;并成功融合了遥控系统和无钥匙系统&#xff0c;沿用了传统…...

怎么找矩阵系统,怎么源码搭建,源头技术开发需要哪些支持

一、引言 在进行矩阵系统源码搭建时&#xff0c;选择合适的工具至关重要。正确的工具选择不仅可以提高开发效率&#xff0c;还能确保系统的稳定性、可扩展性和性能。本文将探讨在矩阵系统源码搭建过程中如何选择合适的工具。 二、前端开发工具选择 前端框架 React&#xff1a;由…...

云原生化 - 工具镜像(简约版)

在微服务和云原生环境中&#xff0c;容器化的目标之一是尽可能保持镜像小型化以提高启动速度和减少安全风险。然而&#xff0c;在实际操作中&#xff0c;有时候需要临时引入一些工具来进行调试、监控或问题排查。Kubernetes提供了临时容器&#xff08;ephemeral containers&…...

uni-app如何搭建项目(一步一步教程)

来来来&#xff0c;看这里 uni-app新建项目教程uni-app项目结构 首先我们要有一个HBuilder这个软件&#xff0c;然后我们来搭建uni-app项目 uni-app新建项目教程 首先我们打开这个HBuilder软件&#xff0c;好我们就出现这个界面&#xff0c;我们点击新建项目   然后我们选择…...

javascript中原型链(__proto__)与原型(prototype)

JavaScript中原型链(proto)与原型(prototype) 在JavaScript中&#xff0c;理解原型链&#xff08;__proto__&#xff09;和原型&#xff08;prototype&#xff09;对于深入掌握面向对象编程至关重要。本文将通过示例代码&#xff0c;详细解析__proto__和prototype之间的关系&a…...

基于多种机器学习的酒店客户流失预测模型的研究与实现

文章目录 有需要本项目的代码或文档以及全部资源&#xff0c;或者部署调试可以私信博主项目介绍实现过程 有需要本项目的代码或文档以及全部资源&#xff0c;或者部署调试可以私信博主 项目介绍 项目背景&#xff1a; 在当今竞争激烈的酒店行业中&#xff0c;预测和防止客户流…...

Unity实现自定义图集(三)

以下内容是根据Unity 2020.1.0f1版本进行编写的   1、实现编辑器模式下进游戏前Pack全部自定义图集 同Unity的图集一样,Unity的编辑器模式会在进游戏前把全部的SpriteAtlas都打一次图集,如图: 我们也实现这样的效果。 首先需要获取全部的图集路径。因为目前使用的是以.…...

【测开面试真题】

针对地图导航设计测试用例 文章目录 1. selenium 定位元素的方式有几种&#xff1f;2. 自动化测试能够取代人工测试吗&#xff1f;3. 什么是回归测试&#xff1f; 1. selenium 定位元素的方式有几种&#xff1f; &#x1f427;①通过CSS选择器定位&#xff1b;&#x1f427;②…...

RelationGraph实现工单进度图——js技能提升

直接上图&#xff1a; 从上图中可以看到整个工单的进度是从【开始】指向【PCB判责】【完善客诉】【PCBA列表】&#xff0c;同时【完善客诉】又可以同时指向【PCB判责】【PCBA列表】&#xff0c;后续各自指向自己的进度。 直接上代码&#xff1a; 1.安装 1.1 Npm 方式 npm …...

针对脚本爬虫攻击的防御策略与实现

随着互联网的发展&#xff0c;网站和应用程序面临着越来越多的自动化攻击&#xff0c;其中包括使用脚本进行的大规模数据抓取&#xff0c;即所谓的“爬虫攻击”。这类攻击不仅影响网站性能&#xff0c;还可能导致敏感数据泄露。本文将探讨如何识别爬虫攻击&#xff0c;并提供一…...

JVM发展历程

JVM发展历程 Sun Classic VM 早在1996年Java1.0版本的时候&#xff0c;Sun公司发布了一款名为sun classic VM的Java虚拟机&#xff0c;它同时也是世界上第一款商用Java虚拟机&#xff0c;JDK1.4时完全被淘汰。这款虚拟机内部只提供解释器。现在还有及时编译器&#xff0c;因此…...

C语言 | Leetcode C语言题解之第470题用Rand7()实现Rand10()

题目&#xff1a; 题解&#xff1a; // The rand7() API is already defined for you. // int rand7(); // return a random integer in the range 1 to 7int rand10() {while(true) {int index (rand7() - 1) * 7 rand7(); if(index < 40) return index % 10 1; } }...

【JavaScript】拷贝对象的几种方式与对比

#工作中拷贝对象是常有的事&#xff0c;我们需要分清楚深浅拷贝&#xff0c;一般来说要做的都是深拷贝&#xff0c;不然会有关联影响# 解构赋值 es6新语法&#xff0c;简洁是简洁&#xff0c;但是需要注意深拷贝只针对第一层 使用方式&#xff1a;{...obj} let stu {name:…...

高防服务器为何有时难以防御CC攻击及其对策

高防服务器通常被用来抵御各种类型的DDoS攻击&#xff0c;包括CC&#xff08;Challenge Collapsar&#xff09;攻击。然而&#xff0c;在某些情况下&#xff0c;即使是配备了高级防护措施的高防服务器也可能难以完全防御CC攻击。本文将探讨导致这一现象的原因&#xff0c;并提供…...

XCTF-web-easyupload

试了试php&#xff0c;php7&#xff0c;pht&#xff0c;phtml等&#xff0c;都没有用 尝试.user.ini 抓包修改将.user.ini修改为jpg图片 在上传一个123.jpg 用蚁剑连接&#xff0c;得到flag...

synchronized 学习

学习源&#xff1a; https://www.bilibili.com/video/BV1aJ411V763?spm_id_from333.788.videopod.episodes&vd_source32e1c41a9370911ab06d12fbc36c4ebc 1.应用场景 不超卖&#xff0c;也要考虑性能问题&#xff08;场景&#xff09; 2.常见面试问题&#xff1a; sync出…...

为什么需要建设工程项目管理?工程项目管理有哪些亮点功能?

在建筑行业&#xff0c;项目管理的重要性不言而喻。随着工程规模的扩大、技术复杂度的提升&#xff0c;传统的管理模式已经难以满足现代工程的需求。过去&#xff0c;许多企业依赖手工记录、口头沟通和分散的信息管理&#xff0c;导致效率低下、成本失控、风险频发。例如&#…...

生成 Git SSH 证书

&#x1f511; 1. ​​生成 SSH 密钥对​​ 在终端&#xff08;Windows 使用 Git Bash&#xff0c;Mac/Linux 使用 Terminal&#xff09;执行命令&#xff1a; ssh-keygen -t rsa -b 4096 -C "your_emailexample.com" ​​参数说明​​&#xff1a; -t rsa&#x…...

高防服务器能够抵御哪些网络攻击呢?

高防服务器作为一种有着高度防御能力的服务器&#xff0c;可以帮助网站应对分布式拒绝服务攻击&#xff0c;有效识别和清理一些恶意的网络流量&#xff0c;为用户提供安全且稳定的网络环境&#xff0c;那么&#xff0c;高防服务器一般都可以抵御哪些网络攻击呢&#xff1f;下面…...

根据万维钢·精英日课6的内容,使用AI(2025)可以参考以下方法:

根据万维钢精英日课6的内容&#xff0c;使用AI&#xff08;2025&#xff09;可以参考以下方法&#xff1a; 四个洞见 模型已经比人聪明&#xff1a;以ChatGPT o3为代表的AI非常强大&#xff0c;能运用高级理论解释道理、引用最新学术论文&#xff0c;生成对顶尖科学家都有用的…...

第 86 场周赛:矩阵中的幻方、钥匙和房间、将数组拆分成斐波那契序列、猜猜这个单词

Q1、[中等] 矩阵中的幻方 1、题目描述 3 x 3 的幻方是一个填充有 从 1 到 9 的不同数字的 3 x 3 矩阵&#xff0c;其中每行&#xff0c;每列以及两条对角线上的各数之和都相等。 给定一个由整数组成的row x col 的 grid&#xff0c;其中有多少个 3 3 的 “幻方” 子矩阵&am…...

SAP学习笔记 - 开发26 - 前端Fiori开发 OData V2 和 V4 的差异 (Deepseek整理)

上一章用到了V2 的概念&#xff0c;其实 Fiori当中还有 V4&#xff0c;咱们这一章来总结一下 V2 和 V4。 SAP学习笔记 - 开发25 - 前端Fiori开发 Remote OData Service(使用远端Odata服务)&#xff0c;代理中间件&#xff08;ui5-middleware-simpleproxy&#xff09;-CSDN博客…...

IP如何挑?2025年海外专线IP如何购买?

你花了时间和预算买了IP&#xff0c;结果IP质量不佳&#xff0c;项目效率低下不说&#xff0c;还可能带来莫名的网络问题&#xff0c;是不是太闹心了&#xff1f;尤其是在面对海外专线IP时&#xff0c;到底怎么才能买到适合自己的呢&#xff1f;所以&#xff0c;挑IP绝对是个技…...

【笔记】WSL 中 Rust 安装与测试完整记录

#工作记录 WSL 中 Rust 安装与测试完整记录 1. 运行环境 系统&#xff1a;Ubuntu 24.04 LTS (WSL2)架构&#xff1a;x86_64 (GNU/Linux)Rust 版本&#xff1a;rustc 1.87.0 (2025-05-09)Cargo 版本&#xff1a;cargo 1.87.0 (2025-05-06) 2. 安装 Rust 2.1 使用 Rust 官方安…...