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

Leetcode.560 和为 K 的子数组

题目链接

Leetcode.560 和为 K 的子数组 mid

题目描述

给你一个整数数组 n u m s nums nums 和一个整数 k k k ,请你统计并返回 该数组中和为 k k k 的子数组的个数

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

示例 1:

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

示例 2:

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

提示:
  • 1 ≤ n u m s . l e n g t h ≤ 2 ∗ 1 0 4 1 \leq nums.length \leq 2 * 10^4 1nums.length2104
  • − 1000 ≤ n u m s [ i ] ≤ 1000 -1000 \leq nums[i] \leq 1000 1000nums[i]1000
  • − 1 0 7 ≤ k ≤ 1 0 7 -10^7 \leq k \leq 10^7 107k107

解法:前缀和 + 哈希表

我们假设 [ j , i ] [j,i] [j,i] 区间的子数组元素和为 k k k,即 :

n u m s [ j ] + n u m s [ j + 1 ] + . . . + n u m s [ i − 1 ] + n u m s [ i ] = k nums[j] + nums[j + 1] + ... + nums[i-1] + nums[i] = k nums[j]+nums[j+1]+...+nums[i1]+nums[i]=k

我们用 s u m sum sum 表示 n u m s nums nums 的前缀和数组,可将上式转换为:

s u m [ i ] − s u m [ j − 1 ] = k sum[i] - sum[j-1] = k sum[i]sum[j1]=k

再转换一下得到:

s u m [ j − 1 ] = s u m [ i ] − k sum[j-1] = sum[i] - k sum[j1]=sum[i]k

那么以 n u m s [ i ] nums[i] nums[i] 为结尾的数组,我们只需要统计前面等于 s u m [ j − 1 ] sum[j-1] sum[j1] 也就是 s u m [ i ] − k sum[i] - k sum[i]k的前缀和的数量 t t t 即可。

那么这个 t t t 就是以 n u m s [ i ] nums[i] nums[i] 为结尾的数组中 和为 k k k 的子数组的数量。

我们只需要对每一个 n u m s [ i ] nums[i] nums[i] 都加上 t t t 即可,这样我们就可以统计出所有的 和为 k k k 的子数组的数量。

在实现上,我们使用哈希表来记录前缀和出现的次数。初始时,和为 0 0 0 ,也需要统计它的出现次数,即 { 0 , 1 } \{ 0 , 1 \} {0,1}

时间复杂度: O ( n ) O(n) O(n)

C++代码:

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

相关文章:

Leetcode.560 和为 K 的子数组

题目链接 Leetcode.560 和为 K 的子数组 mid 题目描述 给你一个整数数组 n u m s nums nums 和一个整数 k k k &#xff0c;请你统计并返回 该数组中和为 k k k 的子数组的个数 。 子数组是数组中元素的连续非空序列。 示例 1&#xff1a; 输入&#xff1a;nums [1,1,1]…...

linklab phase1 更简单的方法

直接反汇编phase1.o&#xff0c;看eax中是0x21&#xff0c;0x21在数据域中&#xff0c;直接把从第21个字节的内容改为0000000000即可。...

8.前端--CSS-文本属性【2023.11.26】

CSS Text&#xff08;文本&#xff09;属性可定义文本的外观&#xff0c;比如文本的颜色、对齐文本、修饰文本、文本缩进、行间距等 1.文本颜色 color 属性用于定义文本的颜色。 语法&#xff1a; div { color: red; }属性&#xff1a; 2.文本对齐 text-align 属性用于设置元…...

容器技术——Cgroup

目录 容器技术容器技术概述要区分好共享与隔离的概念容器技术的三大核心容器对比虚拟机 namespaceUnionFs容器操作系统的来源操作系统的来源完整操作系统的镜像docker image是什么&#xff1f;如何构成的 如何为容器安装操作系统UnionFS&#xff08;联合文件系统&#xff09;的…...

uniapp+vue3路由跳转传参

在uni-app中使用Vue 3进行路由跳转传参&#xff0c;可以通过以下步骤实现&#xff1a; 1.在router文件夹中创建一个名为index.js的文件&#xff0c;用于配置路由。在这个文件中&#xff0c;我们将导入createRouter和createWebHistory函数&#xff0c;并定义路由规则。同时&…...

流量主如何在广告收益和用户体验中找到平衡

流量主在广告收益和用户体验之间找到平衡是一个关键的挑战&#xff0c;因为过多或不恰当的广告可能会影响到用户的满意度和留存率。以下是一些方法&#xff0c;可以帮助流量主在这两者之间找到平衡&#xff1a; admaoyan猫眼聚合 优质内容为先&#xff1a; 提供高质量、有价值的…...

RPC和HTTP的区别

目录 1、RPC是什么 1.1 概念 1.2 RPC的组成部分 1.3 常见的 RPC 技术和框架 1.4 RPC的工作流程 2、HTTP是什么 2.1 概念 2.2 HTTP的消息格式 2.3 HTTP响应状态码有哪些 3、⭐RPC和HTTP的区别 小结 1、RPC是什么 1.1 概念 RPC&#xff08;Remote Procedure Call&am…...

Dubbo3使用Zookeeper作为注册中心的方案讨论!详解DubboAdmin与PrettyZoo来监控服务的优劣!

文章目录 一&#xff1a;Dubbo注册中心的基本使用 二&#xff1a;Zookeeper注册中心的使用 1&#xff1a;依赖引入 2&#xff1a;实际开发 三&#xff1a;Zookeeper作为注册中心的使用展示 1&#xff1a;启动注册Zookeeper服务 2&#xff1a;引入注册中心 (一)&#xf…...

前端uni微信小程序和后端nodejs使用websoket

需求 前端向后台服务器发请求获取验证码&#xff0c;然后端游输入验证码&#xff0c;向我的后端发请求获取验证信息。后台给游戏端返回信息的时候同时给微信小程序端返回验证结果。意思是不要微信小程序端主动触发&#xff0c;验证是否绑定的请求。 思路 后端生成验证码时存…...

java小游戏之【王者荣耀】

首先创建一个新的Java项目命名为“王者荣耀”&#xff0c;并在src下创建两个包分别命名为“com.sxt"、”com.stx.beast",在相应的包中创建所需的类。 代码 package com.sxt;import javax.swing.*; import java.awt.*;public class Background extends GameObject {p…...

QT网络协议知识体系(一)

//获取主机的名称和ip地址 //获取主机的所有信息...

【数据库】表的连接在执行时的算法解析,嵌套循环连接算法的几种实现,多表连接中表的数量会影响什么

嵌套循环连接 ​专栏内容&#xff1a; 手写数据库toadb 本专栏主要介绍如何从零开发&#xff0c;开发的步骤&#xff0c;以及开发过程中的涉及的原理&#xff0c;遇到的问题等&#xff0c;让大家能跟上并且可以一起开发&#xff0c;让每个需要的人成为参与者。 本专栏会定期更新…...

【刷新:重新发现商业与未来】书笔记

收获 同理心&#xff1a;站在他人角度考虑他人感受&#xff0c;他人需要什么&#xff0c;我能提供什么&#xff1b;他人可以是员工&#xff0c;家人等&#xff1b;对于员工来讲核心四件事&#xff1a;1、薪水&#xff1b;2、有结果&#xff1b;3、有成长&#xff1b;4、工作开…...

Lua实现面向对象三大特性

面向对象是基于table实现的 封装 :(冒号) 自动将调用该函数的对象作为第一个参数传入 --Object就是第一参数 function Object:new() self&#xff1a;代表默认传入的第一个参数 _index&#xff1a;当自己的变量中找不到时&#xff0c;会默认找原表中_index指向的内容 Obj…...

竞赛python区块链实现 - proof of work工作量证明共识算法

文章目录 0 前言1 区块链基础1.1 比特币内部结构1.2 实现的区块链数据结构1.3 注意点1.4 区块链的核心-工作量证明算法1.4.1 拜占庭将军问题1.4.2 解决办法1.4.3 代码实现 2 快速实现一个区块链2.1 什么是区块链2.2 一个完整的快包含什么2.3 什么是挖矿2.4 工作量证明算法&…...

C#结合JavaScript实现上传视频到腾讯云点播平台

目录 需求 关键代码 界面元素布局 C# 实现服务端的签名类 上传视频的JS实现 视频演示 小结 需求 在云培训系统里&#xff0c;制作视频课件是我们的主要工作之一&#xff0c;制作完成后如果将这些素材存储到服务器并进行分发播放&#xff0c;是摆在我们面前的一个问题。…...

简单介绍一下js中的构造函数、原型对象prototype、对象原型__proto__、原型链

构造函数 function Star (uname, age){this.uname unamethis.age agethis.sing function(){ log(唱歌~) }}let xzq new Star(薛之谦, 30)let ldh new Star(刘德华, 20)log(ldh) // { uname: 刘德华, age: 20, sing: f }ldh.sing() // 唱歌~log(ldh.sing xzq.sing) // fal…...

Java基于springboot+vue开发服装商城小程序

演示视频&#xff1a; 小程序 https://www.bilibili.com/video/BV1rM411o7m4/?share_sourcecopy_web&vd_source11344bb73ef9b33550b8202d07ae139b 管理员 https://www.bilibili.com/video/BV1fc411D7V3/?share_sourcecopy_web&vd_source11344bb73ef9b33550b8202d07ae…...

设计模式之十二:复合模式

模式通常被一起使用&#xff0c;并被组合在同一个解决方案中。 复合模式在一个解决方案中结合两个或多个模式&#xff0c;以解决一般或重复发生的问题。 首先重新构建鸭子模拟器&#xff1a; package headfirst.designpatterns.combining.ducks;public interface Quackable …...

java通过年月获取当前月所有周(跨月),获取每周开始日期和结束日期

/*** 根据年月返回本月共几周&#xff0c;每周开始与结束日期*/public static List<Map<String, String>> queryWeek(String year, String month) throws ParseException {/** 周 **/final String[] weeks { "第一周", "第二周", "第…...

使用VSCode开发Django指南

使用VSCode开发Django指南 一、概述 Django 是一个高级 Python 框架&#xff0c;专为快速、安全和可扩展的 Web 开发而设计。Django 包含对 URL 路由、页面模板和数据处理的丰富支持。 本文将创建一个简单的 Django 应用&#xff0c;其中包含三个使用通用基本模板的页面。在此…...

使用分级同态加密防御梯度泄漏

抽象 联邦学习 &#xff08;FL&#xff09; 支持跨分布式客户端进行协作模型训练&#xff0c;而无需共享原始数据&#xff0c;这使其成为在互联和自动驾驶汽车 &#xff08;CAV&#xff09; 等领域保护隐私的机器学习的一种很有前途的方法。然而&#xff0c;最近的研究表明&…...

【ROS】Nav2源码之nav2_behavior_tree-行为树节点列表

1、行为树节点分类 在 Nav2(Navigation2)的行为树框架中,行为树节点插件按照功能分为 Action(动作节点)、Condition(条件节点)、Control(控制节点) 和 Decorator(装饰节点) 四类。 1.1 动作节点 Action 执行具体的机器人操作或任务,直接与硬件、传感器或外部系统…...

华为OD机试-食堂供餐-二分法

import java.util.Arrays; import java.util.Scanner;public class DemoTest3 {public static void main(String[] args) {Scanner in new Scanner(System.in);// 注意 hasNext 和 hasNextLine 的区别while (in.hasNextLine()) { // 注意 while 处理多个 caseint a in.nextIn…...

PL0语法,分析器实现!

简介 PL/0 是一种简单的编程语言,通常用于教学编译原理。它的语法结构清晰,功能包括常量定义、变量声明、过程(子程序)定义以及基本的控制结构(如条件语句和循环语句)。 PL/0 语法规范 PL/0 是一种教学用的小型编程语言,由 Niklaus Wirth 设计,用于展示编译原理的核…...

AI编程--插件对比分析:CodeRider、GitHub Copilot及其他

AI编程插件对比分析&#xff1a;CodeRider、GitHub Copilot及其他 随着人工智能技术的快速发展&#xff0c;AI编程插件已成为提升开发者生产力的重要工具。CodeRider和GitHub Copilot作为市场上的领先者&#xff0c;分别以其独特的特性和生态系统吸引了大量开发者。本文将从功…...

学习STC51单片机32(芯片为STC89C52RCRC)OLED显示屏2

每日一言 今天的每一份坚持&#xff0c;都是在为未来积攒底气。 案例&#xff1a;OLED显示一个A 这边观察到一个点&#xff0c;怎么雪花了就是都是乱七八糟的占满了屏幕。。 解释 &#xff1a; 如果代码里信号切换太快&#xff08;比如 SDA 刚变&#xff0c;SCL 立刻变&#…...

蓝桥杯3498 01串的熵

问题描述 对于一个长度为 23333333的 01 串, 如果其信息熵为 11625907.5798&#xff0c; 且 0 出现次数比 1 少, 那么这个 01 串中 0 出现了多少次? #include<iostream> #include<cmath> using namespace std;int n 23333333;int main() {//枚举 0 出现的次数//因…...

面向无人机海岸带生态系统监测的语义分割基准数据集

描述&#xff1a;海岸带生态系统的监测是维护生态平衡和可持续发展的重要任务。语义分割技术在遥感影像中的应用为海岸带生态系统的精准监测提供了有效手段。然而&#xff0c;目前该领域仍面临一个挑战&#xff0c;即缺乏公开的专门面向海岸带生态系统的语义分割基准数据集。受…...

基于SpringBoot在线拍卖系统的设计和实现

摘 要 随着社会的发展&#xff0c;社会的各行各业都在利用信息化时代的优势。计算机的优势和普及使得各种信息系统的开发成为必需。 在线拍卖系统&#xff0c;主要的模块包括管理员&#xff1b;首页、个人中心、用户管理、商品类型管理、拍卖商品管理、历史竞拍管理、竞拍订单…...