当前位置: 首页 > 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;并提供…...

超短脉冲激光自聚焦效应

前言与目录 强激光引起自聚焦效应机理 超短脉冲激光在脆性材料内部加工时引起的自聚焦效应&#xff0c;这是一种非线性光学现象&#xff0c;主要涉及光学克尔效应和材料的非线性光学特性。 自聚焦效应可以产生局部的强光场&#xff0c;对材料产生非线性响应&#xff0c;可能…...

ubuntu搭建nfs服务centos挂载访问

在Ubuntu上设置NFS服务器 在Ubuntu上&#xff0c;你可以使用apt包管理器来安装NFS服务器。打开终端并运行&#xff1a; sudo apt update sudo apt install nfs-kernel-server创建共享目录 创建一个目录用于共享&#xff0c;例如/shared&#xff1a; sudo mkdir /shared sud…...

相机Camera日志实例分析之二:相机Camx【专业模式开启直方图拍照】单帧流程日志详解

【关注我&#xff0c;后续持续新增专题博文&#xff0c;谢谢&#xff01;&#xff01;&#xff01;】 上一篇我们讲了&#xff1a; 这一篇我们开始讲&#xff1a; 目录 一、场景操作步骤 二、日志基础关键字分级如下 三、场景日志如下&#xff1a; 一、场景操作步骤 操作步…...

如何在看板中体现优先级变化

在看板中有效体现优先级变化的关键措施包括&#xff1a;采用颜色或标签标识优先级、设置任务排序规则、使用独立的优先级列或泳道、结合自动化规则同步优先级变化、建立定期的优先级审查流程。其中&#xff0c;设置任务排序规则尤其重要&#xff0c;因为它让看板视觉上直观地体…...

论文浅尝 | 基于判别指令微调生成式大语言模型的知识图谱补全方法(ISWC2024)

笔记整理&#xff1a;刘治强&#xff0c;浙江大学硕士生&#xff0c;研究方向为知识图谱表示学习&#xff0c;大语言模型 论文链接&#xff1a;http://arxiv.org/abs/2407.16127 发表会议&#xff1a;ISWC 2024 1. 动机 传统的知识图谱补全&#xff08;KGC&#xff09;模型通过…...

使用Matplotlib创建炫酷的3D散点图:数据可视化的新维度

文章目录 基础实现代码代码解析进阶技巧1. 自定义点的大小和颜色2. 添加图例和样式美化3. 真实数据应用示例实用技巧与注意事项完整示例(带样式)应用场景在数据科学和可视化领域,三维图形能为我们提供更丰富的数据洞察。本文将手把手教你如何使用Python的Matplotlib库创建引…...

【前端异常】JavaScript错误处理:分析 Uncaught (in promise) error

在前端开发中&#xff0c;JavaScript 异常是不可避免的。随着现代前端应用越来越多地使用异步操作&#xff08;如 Promise、async/await 等&#xff09;&#xff0c;开发者常常会遇到 Uncaught (in promise) error 错误。这个错误是由于未正确处理 Promise 的拒绝&#xff08;r…...

Spring Security 认证流程——补充

一、认证流程概述 Spring Security 的认证流程基于 过滤器链&#xff08;Filter Chain&#xff09;&#xff0c;核心组件包括 UsernamePasswordAuthenticationFilter、AuthenticationManager、UserDetailsService 等。整个流程可分为以下步骤&#xff1a; 用户提交登录请求拦…...

pycharm 设置环境出错

pycharm 设置环境出错 pycharm 新建项目&#xff0c;设置虚拟环境&#xff0c;出错 pycharm 出错 Cannot open Local Failed to start [powershell.exe, -NoExit, -ExecutionPolicy, Bypass, -File, C:\Program Files\JetBrains\PyCharm 2024.1.3\plugins\terminal\shell-int…...

PH热榜 | 2025-06-08

1. Thiings 标语&#xff1a;一套超过1900个免费AI生成的3D图标集合 介绍&#xff1a;Thiings是一个不断扩展的免费AI生成3D图标库&#xff0c;目前已有超过1900个图标。你可以按照主题浏览&#xff0c;生成自己的图标&#xff0c;或者下载整个图标集。所有图标都可以在个人或…...