累加和为 K 的最长子数组问题
2024-09-05 17:15:31
累加和为 K 的最长子数组问题
作者:Grey
原文地址:
题目描述
给定一个整数组成的无序数组 arr,值可能正、可能负、可能0,给定一个整数值 K,找到 arr 的所有子数组里,哪个子数组的累加和等于 K,并且是长度最大的,返回其长度。
OJ 见:LintCode 911 · Maximum Size Subarray Sum Equals k
主要思路
使用哈希表,key 存累加和,value 存当前位置,所以,
map.put(sum,i)
表示0...i
的累加和是sum
。
有了这个哈希表,我们可以继续遍历数组,当遍历到i
位置的时候,我们可以得到当前的累加和是sum
,我们期待哈希表中是否存在sum - k
的记录,如果有,说明
i - map.get(sum - k)
就是一个可能的答案,示例图如下
我们每次来到一个i
位置,就要定位上图中m
的位置,即i - map.get(sum-k)
的值。
然后和全局答案进行比较,抓取最大长度即可。
代码见:
public class Solution {
public static int maxSubArrayLen(int[] arr, int k) {
if (arr == null) {
return 0;
}
Map<Integer, Integer> map = new HashMap<>();
map.put(0, -1);
int ans = 0;
int sum = 0;
for (int i = 0; i < arr.length; i++) {
sum += arr[i];
// 期待map里面有sum - k的记录
if (map.containsKey(sum - k)) {
ans = Math.max(ans, i - map.get(sum - k));
}
if (!map.containsKey(sum)) {
map.put(sum, i);
}
}
return ans;
}
}
注:map.put(0, -1);
这一句很有必要,表示在一个元素都没有的情况下,已经可以得到一个累加和为 0 的数组了。
整个算法的时间复杂度是O(N)
,空间复杂度O(N)
。
有了上述算法模型,面对这题: LeetCode 525. Contiguous Array
给定一个整数组成的无序数组 arr,值可能正、可能负、可能0,找到 arr 的所有子数组里,数组中 1 和 0 一样多的子数组最长的长度
只需要预处理一下原数组,遇到0变为-1,遇到1保持1,遇到其他变为0,接下来求子数组之和为0的最大子数组长度,复用上述算法模板即可。
代码如下
class Solution {
public static int findMaxLength(int[] arr) {
for (int i = 0; i < arr.length; i++) {
if (arr[i] == 0) {
arr[i] = -1;
}
}
// 转换为累加和等于K的最长子数组长度
Map<Integer, Integer> map = new HashMap<>(arr.length);
map.put(0, -1);
int ans = 0;
int sum = 0;
for (int i = 0; i < arr.length; i++) {
sum += arr[i];
if (map.containsKey(sum)) {
ans = Math.max(ans, i - map.get(sum));
}
if (!map.containsKey(sum)) {
map.put(sum, i);
}
}
return ans;
}
}
更多
最新文章
- 孙鑫MFC学习笔记12:文件读写
- CSS-布局【1】-图片在div中垂直居中
- Unity3d优化
- Git Permission denied (publickey).
- 类,抽象基类,接口类三者间的区别与联系(C++)
- Struct2提交表单数据到Acion
- ANDROID_MARS学习笔记_S01原始版_002_实现计算乘积及menu应用
- 关于windows服务的操作
- hdu1428之dfs+spfa
- logstash+ElasticSearch+Kibana VS Splunk
- linux跨主机复制文件或文件夹
- SpringMVC中Controller的方法返回值
- 算法与数据结构(八) AOV网的关键路径(Swift版)
- 推荐一个Monokai风格的EditPlus配色方案
- Archlinux安装指南~小米笔记本Air 13.3英寸版本
- LOJ#6282. 数列分块入门 6
- js -- 绑定的click addEventListener 事件只触发一次
- maven 如何引入本地jar包
- Pytorch快速入门及在线体验
- English trip -- VC(情景课)3 A Family
热门文章
- 华为HMS Core携手超图为三维GIS注入新动能
- sqlserver 把c#代码的string[] 的ids转换成一个数据table表
- 【微服务专题之】.Net6下集成消息队列上-RabbitMQ
- VM Ware 给Centos虚拟机配置静态IP
- 【RocketMQ】消息的拉取
- 4-10 CS后台项目练习-3 || Redis
- 86开关、家电、台扇等6键6路6感应通道高抗干扰触摸IC-VK3606D,稳定性好,抗干扰能力强
- Ubu18远程登录密匙设置
- 8月份的.NET Conf 活动 专注于 .NET MAUI
- java日常开发必备:list的四种遍历