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

[Java恶补day10] 560. 和为K的子数组

给你一个整数数组 nums 和一个整数 k ,请你统计并返回 该数组中和为 k 的子数组的个数 。
子数组是数组中元素的连续非空序列

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

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

提示:
1 <= nums.length <= 2 ∗ 10 4 2 * 10^4 2104
-1000 <= nums[i] <= 1000
− 10 7 -10^7 107 <= k <= 10 7 10^7 107


知识点:
数组、哈希表、前缀和


解:
前缀和:s[0]=0, s[i+1]=nums[0]+nums[1]+⋯+nums[i]

题目要求求解有多少个子数组(元素是连续的,原数组也是无序的,并可能出现负值),这就无法使用滑动窗口进行求解,因此考虑前缀和

核心思想:目标是nums[j]-nums[i]=k,i<j。这可通过二重循环暴力求解,但为了考虑复杂度,将目标改为:nums[i]=nums[j]-k。

这里使用先后两个循环:
①第一个循环:计算数组的每个位置上的前缀和(这里要考虑下标0的前缀和=0,因此数组sum的大小=n+1)
②第二个循环:遍历每个前缀和,判断在这个前缀和所对应数组下标的左边,有多少个前缀和=差值nums[j]-k。这里用到一个HashMap。

这里以一个例子进行辅助说明。
令nums=[1,1,-1,1,-1]。
①通过第一个循环,得到n+1个位置上的前缀和:
i=0时,sum[1]=sum[0]+nums[0]=0+1=1
i=1时,sum[2]=sum[1]+nums[1]=1+1=2
i=2时,sum[3]=sum[2]+nums[2]=2+(-1)=1
i=3时,sum[4]=sum[3]+nums[3]=1+1=2
i=4时,sum[5]=sum[4]+nums[4]=2+(-1)=1
所以,sum={0,1,2,1,2,1}
②通过第二个循环:
对于sum[0]=0,k=1,sum[0]-k=0-1=-1,判断map中是否存在key=-1的键值对,显然不存在,所以得到0,res=0+0=0。接着,将前缀和=0存入map,其对应的value=1。
对于sum[1]=1,k=1,sum[1]-k=1-1=0,判断map中是否存在key=0的键值对,存在,获得1,res=0+1=1,表示存在1个,即nums[1]之前恰好有1个满足条件的子数组(nums[0])。接着,将前缀和=1存入map,其对应的value=1。
对于sum[2]=2,k=1,sum[2]-k=2-1=1,判断map中是否存在key=1的键值对,存在,获得1,res=1+1=2,表示存在1个,即nums[2]之前恰好有1个满足条件的子数组(nums[0, 1])。接着,将前缀和=2存入map,其对应的value=1。
对于sum[3]=1,k=1,sum[3]-k=1-1=0,判断map中是否存在key=0的键值对,存在,获得1,res=2+1=3,表示存在1个,即nums[3]之前恰好有1个满足条件的子数组(nums[0,1,2])。接着,将前缀和=1存入map,其对应的value=2。
对于sum[4]=2,k=1,sum[4]-k=2-1=1,判断map中是否存在key=1的键值对,存在,获得2,res=3+2=5,表示存在2个,即nums[4]之前恰好有2个满足条件的子数组(nums[0,1,2]、nums[3])。接着,将前缀和=2存入map,其对应的value=2。
对于sum[5]=1,k=1,sum[5]-k=1-1=0,判断map中是否存在key=0的键值对,存在,获得1,res=5+1=6,表示存在1个,即nums[5]之前(nums[5]对应整个原始数组)恰好有1个满足条件的子数组(nums[0,1,2,3,4])。接着,将前缀和=1存入map,其对应的value=3。
最终,map中元素为:map={0: 1, 1: 3, 2: 2},res=6,所以有6个满足要求的子数组。

时间复杂度: O ( n ) O(n) O(n),遍历整个原始数组一次。
空间复杂度: O ( n ) O(n) O(n),用了长度n+1的int数组和HashMap。

class Solution {public int subarraySum(int[] nums, int k) {//定义变量存储满足条件的子数组数量int res = 0;//数组长度int n = nums.length;//存储前缀和,包括s[0]int[] sum = new int[n + 1];//初始化为0//遍历每个元素,计算前缀和for (int i = 0; i < n; i++) {sum[i + 1] = sum[i] + nums[i];}//定义map存储s[j]-kMap<Integer, Integer> map = new HashMap<>(n + 1);//设置map容量可加速//遍历每个前缀和for (int prefix : sum) {//获取前缀和=prefix-k的出现次数(java8方法)res += map.getOrDefault(prefix - k, 0);//更新当前遍历的前缀和的出现次数if (map.containsKey(prefix)) {map.put(prefix, map.get(prefix) + 1);} else {map.put(prefix, 1);}}return res;}
}

参考:
1、灵神解析
2、java8的getOrDefault()

http://www.xdnf.cn/news/9763.html

相关文章:

  • 每日Prompt:卵石拼画
  • 计算机图形学:(五)坐标系
  • 排序算法-归并排序与快速排序
  • 如何避免客户频繁更换对接人
  • vue3项目 前端文件下载的两种工具函数
  • spring的多语言怎么实现?
  • OSI 七大层详解
  • vue element日期范围选择器只能选择指定天数内的
  • shell脚本实现字符串子网掩码转为位数
  • mqtt协议连接阿里云平台
  • 基于多模态脑电、音频与视觉信号的情感识别算法【Nature核心期刊,EAV:EEG-音频-视频数据集】
  • Deepseek应用技巧-Dify本地化搭建合同审批助手
  • Delphi 导入excel
  • 【东枫科技】KrakenSDR 测向快速入门指南
  • Vision Transformer网络结构
  • 【穷举】数字方格
  • 文件系统与文件管理:从磁盘到内核的全链路解析
  • 高效工具-tldr
  • 网络安全的守护者:iVX 如何构建全方位防护体系
  • 镍钯金PCB有哪些工艺优势?
  • 五、web安全--XSS漏洞(2)--XSS相关payload
  • 《Discuz! X3.5开发从入门到生态共建》第3章 Discuz! X3.5 核心目录结构解析-优雅草卓伊凡
  • Parsel深度解析:从入门到高阶的网页数据抓取艺术
  • python同步mysql数据
  • WPS 免登录解锁编辑
  • 安全访问 std::tuple 的容错方法及气象领域应用
  • R3GAN利用配置好的Pytorch训练自己的数据集
  • Vue-Router中的三种路由历史模式详解
  • MCP入门实战(极简案例)
  • eNSP企业综合网络设计拓扑图