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

力扣-和为K的子数组

题目-和为 K 的子数组

在这里插入图片描述

解法1:两层for循环

public class T560 {public static int subarraySum(int[] nums, int k) {int res = 0;for (int i = 0; i < nums.length; i++) {int tempSum = 0;for (int j = i; j < nums.length; j++) {tempSum += nums[j];if (tempSum == k) {res++;}}}return res;}public static void main(String[] args) {int[] nums = {1, -1, 0};int k = 0;System.out.println(subarraySum(nums, k));}
}

解法2:前缀和+哈希

  • 前缀和:前缀和数组 sum[i] 表示从数组起点到位置 i 的元素之和。
  • 哈希表:使用哈希表记录前缀和出现的次数,这样在遍历数组时可以快速找到符合条件的子数组。
public class T560 {public static int subarraySum(int[] nums, int k) {int res = 0;Map<Integer, Integer> map = new HashMap<>();map.put(0, 1);// int currentSum = 0;for (int i = 0; i < nums.length; i++) {//sum[i...j]=sum[j]-sum[i-1]currentSum += nums[i];if (map.containsKey(currentSum - k)) {res += map.get(currentSum - k);}map.put(currentSum, map.getOrDefault(currentSum, 0) + 1);}return res;}public static void main(String[] args) {int[] nums = {1, -1, 0};int k = 0;System.out.println(subarraySum(nums, k));}
}

详细解释 currentSum - k
设 currentSum 表示当前的前缀和,也就是从数组起点到当前位置的元素之和。我们希望找到一个子数组,使得这个子数组的和等于 k。假设我们当前遍历到数组位置 j,当前的前缀和为 currentSum。

如果存在某个位置 i 使得从 i 到 j 的子数组和等于 k,根据前缀和的定义,有:sum[j]-sum[i-1]=k 其中sum[j]就是currentSum

变形一下:sum[j]-sum[i-1]=k ➡️sum[j]-k=sum[i-1]➡️currentSum-k=sum[i-1]。(因为已知k,不知道sum[i-1] ,所以把k移到等号左边,看map中是否包含sum[i-1],包含则说明ij的和为k


为什么是res += map.get(currentSum - k);而不是res += 1;因为可能存在多个前缀和为currentSum - k。搞懂map存的什么

相关文章:

力扣-和为K的子数组

题目-和为 K 的子数组 解法1&#xff1a;两层for循环 public class T560 {public static int subarraySum(int[] nums, int k) {int res 0;for (int i 0; i < nums.length; i) {int tempSum 0;for (int j i; j < nums.length; j) {tempSum nums[j];if (tempSum k)…...

写一个坏越个人天地(五)

昨天整了半天天气api还是有点小问题。一天50次真的不够我test的。一气之下还是全删了改用高德api。把接口写在了后端&#xff0c;这样我启动界面后就可以直接通过接口在后端嘎嘎处理逻辑了。再整理返回就好了 不过高德api好像获取地址的概率好低&#xff0c;于是我还是整了个获…...

步步精科技诚邀您参加2024慕尼黑上海电子展

尊敬的客户&#xff1a; 我们诚挚地邀请您参加即将于2024年7月8日至7月10日在上海新国际博览中心举办的2024慕尼黑上海电子展&#xff08;electronica China&#xff09;。此次展会汇聚了国内外优秀企业&#xff0c;展示从元器件到系统集成方案的完整产品链&#xff0c;为各行…...

Spring Boot中如何配置和使用多数据源

Spring Boot中如何配置和使用多数据源 大家好&#xff0c;我是免费搭建查券返利机器人省钱赚佣金就用微赚淘客系统3.0的小编&#xff0c;也是冬天不穿秋裤&#xff0c;天冷也要风度的程序猿&#xff01;今天&#xff0c;我们将深入探讨如何在Spring Boot应用中配置和使用多数据…...

vue3 【提效】全局布局 vite-plugin-vue-layouts 实用教程

一个常见的需求是&#xff0c;同模块的若干页面需要使用同一种布局&#xff0c;比如俱乐部相关的页面的顶部需要展示俱乐部的名称&#xff0c;其他页面顶部需要展示网站名称。 通常实现的方法是&#xff0c;将俱乐部的名称和网站名称定义成公共组件&#xff0c;在每个页面都书…...

前端性能优化-实测

PageSpeed Insights 性能测试 今天测试网站性能的时候发现一个问题&#xff0c;一个h2标签内容为什么会占据这么长的渲染时间&#xff0c;甚至有阶段测到占据了7000多毫秒&#xff0c;使用了很多方法都不能解决&#xff0c;包括了修改标签&#xff0c;样式大小等&#xff0c;当…...

【Linux】初识操作系统

一、冯•诺依曼体系结构 在学习操作系统之前&#xff0c;我们先来认识一下冯•诺依曼体系结构&#xff0c;我们常见的计算机&#xff0c;如笔记本。我们不常见的计算机&#xff0c;如服务器&#xff0c;大部分都遵守冯诺依曼体系。 截至目前&#xff0c;我们所认识的计算机&am…...

等保2.0中,如何确保云服务提供商的数据主权合规?

等保2.0中云服务提供商的数据主权合规措施 等保2.0&#xff08;网络安全等级保护2.0&#xff09;是中国的网络安全标准&#xff0c;旨在确保云服务提供商的数据主权合规。以下是一些关键措施和要求&#xff1a; 数据地理位置要求&#xff1a;云服务提供商必须保证所有基础设施位…...

【AI大模型】Transformers大模型库(十四):Datasets Viewer

目录 一、引言 二、Datasets Viewer数据查看器 2.1 概述 2.2 示例 三、总结 一、引言 这里的Transformers指的是huggingface开发的大模型库&#xff0c;为huggingface上数以万计的预训练大模型提供预测、训练等服务。 &#x1f917; Transformers 提供了数以千计的预训练…...

一个例子理解傅里叶变换的计算过程

假设我们有一个简单的信号&#xff0c;由两个不同频率的正弦波组成&#xff0c;我们希望通过傅里叶变换来分析其频谱。 示例信号 假设我们有一个信号 &#xff1a; 这个信号由两个频率成分组成&#xff1a;一个50 Hz的正弦波和一个120 Hz的正弦波&#xff0c;后者的振幅是前者…...

2-2到2-4

计算出所有人的平均年龄&#xff1a; val lines sc.textFile("/root/data/scala/people/page.txt") val count lines.count() val total lines.map(line > line.split(" ")(1)).map(t>t.trim.toInt).collect().reduce((a,b)>ab) val avgAge …...

Vatee万腾平台:一站式智慧服务,让生活更美好

在数字化浪潮席卷全球的今天&#xff0c;我们生活的方方面面都在经历着前所未有的变革。Vatee万腾平台凭借其一站式智慧服务&#xff0c;正成为推动这场变革的重要力量&#xff0c;让我们的生活变得更加美好。 Vatee万腾平台&#xff0c;作为一家专注于提供智慧服务的领军企业&…...

如何选择一个好的汽车油封制造商?

汽车的每一个零部件都至关重要&#xff0c;其中&#xff0c;油封的作用更是不可忽视。它们确保了液体和气体在汽车内部的正确流动&#xff0c;防止了泄漏。因此&#xff0c;选择一个可靠的汽车油封制造商就显得尤为重要。那么&#xff0c;我们应该如何做出明智的选择呢? 首先…...

构建高效的电商返利系统:架构设计与实现

构建高效的电商返利系统&#xff1a;架构设计与实现 大家好&#xff0c;我是免费搭建查券返利机器人省钱赚佣金就用微赚淘客系统3.0的小编&#xff0c;也是冬天不穿秋裤&#xff0c;天冷也要风度的程序猿&#xff01; 电商返利系统作为连接消费者和商家的桥梁&#xff0c;能够…...

如何使用 Python 交互式解释器?

1. 什么是Python交互式解释器&#xff1f; Python交互式解释器是一种REPL&#xff08;Read-Eval-Print Loop&#xff09;环境。它会读取用户输入的代码&#xff0c;执行代码&#xff0c;并输出结果&#xff0c;随后等待下一个用户输入。这种交互方式使得Python非常适合快速原型…...

C++日期类的完整实现,以及this指针的const修饰等的介绍

文章目录 前言一、日期类的实现二、this指针的const修饰总结 前言 C日期类的完整实现&#xff0c;以及this指针的const修饰等的介绍 一、日期类的实现 // Date.h #pragma once#include <iostream> using namespace std;#include <assert.h>class Date {// 友元函…...

缓冲区溢出

本文作者&#xff1a;杉木涂鸦智能安全实验室 前置知识点 栈 栈&#xff08;Stack&#xff09;是计算机中的一种数据结构&#xff0c;用于存储临时数据。它的特点是后入先出&#xff08;LIFO&#xff09;&#xff0c;只能在栈顶添加或删除数据。在程序中&#xff0c;栈被用于…...

step7:“模拟量界面”逻辑

文章目录 文章介绍效果图AnalogPage.qml结构图调用 SerialPortHandler.sendData(message); serialporthandler.cpp 文章介绍 之前的6步实现了案例MF的界面设计和串口界面的逻辑设计&#xff0c;本文将实现模拟量界面的逻辑设计 新增功能&#xff1a; 1&#xff09;弹出提示框 …...

Arduino - 继电器

Arduino - 继电器 In a previous tutorial, we have learned how to turn on/off an LED. In this tutorial, we are going to learn how to turn on/off some kind of devices that use the high voltage power supply(such as a light bulb, fan, electromagnetic lock, lin…...

状态压缩DP——AcWing 327. 玉米田

状态压缩DP 定义 状态压缩 DP 是一种通过二进制压缩状态的动态规划算法。它通过使用位运算来加速状态的转移和计算&#xff0c;从而提高算法的效率。 注意事项 数据范围&#xff1a;状态压缩 DP 通常适用于数据范围较小的问题&#xff0c;因为它需要使用二进制来表示状态&a…...

浅谈 React Hooks

React Hooks 是 React 16.8 引入的一组 API&#xff0c;用于在函数组件中使用 state 和其他 React 特性&#xff08;例如生命周期方法、context 等&#xff09;。Hooks 通过简洁的函数接口&#xff0c;解决了状态与 UI 的高度解耦&#xff0c;通过函数式编程范式实现更灵活 Rea…...

大型活动交通拥堵治理的视觉算法应用

大型活动下智慧交通的视觉分析应用 一、背景与挑战 大型活动&#xff08;如演唱会、马拉松赛事、高考中考等&#xff09;期间&#xff0c;城市交通面临瞬时人流车流激增、传统摄像头模糊、交通拥堵识别滞后等问题。以演唱会为例&#xff0c;暖城商圈曾因观众集中离场导致周边…...

mongodb源码分析session执行handleRequest命令find过程

mongo/transport/service_state_machine.cpp已经分析startSession创建ASIOSession过程&#xff0c;并且验证connection是否超过限制ASIOSession和connection是循环接受客户端命令&#xff0c;把数据流转换成Message&#xff0c;状态转变流程是&#xff1a;State::Created 》 St…...

Python爬虫实战:研究feedparser库相关技术

1. 引言 1.1 研究背景与意义 在当今信息爆炸的时代,互联网上存在着海量的信息资源。RSS(Really Simple Syndication)作为一种标准化的信息聚合技术,被广泛用于网站内容的发布和订阅。通过 RSS,用户可以方便地获取网站更新的内容,而无需频繁访问各个网站。 然而,互联网…...

Opencv中的addweighted函数

一.addweighted函数作用 addweighted&#xff08;&#xff09;是OpenCV库中用于图像处理的函数&#xff0c;主要功能是将两个输入图像&#xff08;尺寸和类型相同&#xff09;按照指定的权重进行加权叠加&#xff08;图像融合&#xff09;&#xff0c;并添加一个标量值&#x…...

跨链模式:多链互操作架构与性能扩展方案

跨链模式&#xff1a;多链互操作架构与性能扩展方案 ——构建下一代区块链互联网的技术基石 一、跨链架构的核心范式演进 1. 分层协议栈&#xff1a;模块化解耦设计 现代跨链系统采用分层协议栈实现灵活扩展&#xff08;H2Cross架构&#xff09;&#xff1a; 适配层&#xf…...

10-Oracle 23 ai Vector Search 概述和参数

一、Oracle AI Vector Search 概述 企业和个人都在尝试各种AI&#xff0c;使用客户端或是内部自己搭建集成大模型的终端&#xff0c;加速与大型语言模型&#xff08;LLM&#xff09;的结合&#xff0c;同时使用检索增强生成&#xff08;Retrieval Augmented Generation &#…...

从“安全密码”到测试体系:Gitee Test 赋能关键领域软件质量保障

关键领域软件测试的"安全密码"&#xff1a;Gitee Test如何破解行业痛点 在数字化浪潮席卷全球的今天&#xff0c;软件系统已成为国家关键领域的"神经中枢"。从国防军工到能源电力&#xff0c;从金融交易到交通管控&#xff0c;这些关乎国计民生的关键领域…...

实战三:开发网页端界面完成黑白视频转为彩色视频

​一、需求描述 设计一个简单的视频上色应用&#xff0c;用户可以通过网页界面上传黑白视频&#xff0c;系统会自动将其转换为彩色视频。整个过程对用户来说非常简单直观&#xff0c;不需要了解技术细节。 效果图 ​二、实现思路 总体思路&#xff1a; 用户通过Gradio界面上…...

SQL Server 触发器调用存储过程实现发送 HTTP 请求

文章目录 需求分析解决第 1 步:前置条件,启用 OLE 自动化方式 1:使用 SQL 实现启用 OLE 自动化方式 2:Sql Server 2005启动OLE自动化方式 3:Sql Server 2008启动OLE自动化第 2 步:创建存储过程第 3 步:创建触发器扩展 - 如何调试?第 1 步:登录 SQL Server 2008第 2 步…...