前缀和 & 哈希表求解连续数组

简介: 前缀和 & 哈希表求解连续数组

网络异常,图片无法展示
|


题目描述



这是 LeetCode 上的 525. 连续数组 ,难度为 中等


Tag : 「前缀和」


给定一个二进制数组 nums , 找到含有相同数量的 0 和 1 的最长连续子数组,并返回该子数组的长度。


示例 1:


输入: nums = [0,1]
输出: 2
说明: [0, 1] 是具有相同数量0和1的最长连续子数组。
复制代码


示例 2:


输入: nums = [0,1,0]
输出: 2
说明: [0, 1] (或 [1, 0]) 是具有相同数量0和1的最长连续子数组。
复制代码


提示:


  • 1 <= nums.length <= 10^5105
  • nums[i] 不是 0 就是 1


基本分析



根据题意,我们可以轻易发现如下性质:


  • 如果答案非 00,那么子数组长度必然为偶数,且长度至少为 22


前缀和 + 哈希表



具体的,我们在预处理前缀和时,将 nums[i]nums[i]00 的值当做 -11 处理。


从而将问题转化为:如何求得最长一段区间和为 00 的子数组。


同时使用「哈希表」来记录「某个前缀和出现的最小下标」是多少。


再结合「如果答案非 00,子数组长度至少为 22」的特性,我们让循环从 22 开始,并在循环开始前往「哈希表」存入哨兵,从而实现不需要处理边界问题。


PS. 哈希表常数还是比较大的,用数组模拟哈希表的卡常代码见 P2。


代码:


class Solution {
    public int findMaxLength(int[] nums) {
        int n = nums.length;
        int[] sum = new int[n + 1];
        for (int i = 1; i <= n; i++) sum[i] = sum[i - 1] + (nums[i - 1] == 1 ? 1 : -1);
        int ans = 0;
        Map<Integer, Integer> map = new HashMap<>();
        map.put(0, 0);
        for (int i = 2; i <= n; i++) {
            if (!map.containsKey(sum[i - 2])) map.put(sum[i - 2], i - 2);
            if (map.containsKey(sum[i])) ans = Math.max(ans, i - map.get(sum[i]));
        }
        return ans;
    }
}
复制代码


class Solution {
    public int findMaxLength(int[] nums) {
        int n = nums.length;
        int[] sum = new int[n + 1];
        for (int i = 1; i <= n; i++) sum[i] = sum[i - 1] + (nums[i - 1] == 1 ? 1 : -1);
        int ans = 0;
        int[] hash = new int[2 * n + 1];
        Arrays.fill(hash, -1);
        hash[0 + n] = 0;
        for (int i = 2; i <= n; i++) {
            if (hash[sum[i - 2] + n] == -1) hash[sum[i - 2] + n] = i - 2;
            if (hash[sum[i] + n] != -1) ans = Math.max(ans, i - hash[sum[i] + n]);
        }
        return ans;
    }
}
复制代码


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


最后



这是我们「刷穿 LeetCode」系列文章的第 No.525 篇,系列开始于 2021/01/01,截止于起始日 LeetCode 上共有 1916 道题目,部分是有锁题,我们将先将所有不带锁的题目刷完。


在这个系列文章里面,除了讲解解题思路以外,还会尽可能给出最为简洁的代码。如果涉及通解还会相应的代码模板。


为了方便各位同学能够电脑上进行调试和提交代码,我建立了相关的仓库:github.com/SharingSour…


在仓库地址里,你可以看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其他优选题解。

相关文章
|
SQL 缓存 Java
如何判断mybatis 开启二级缓存 和二级缓存详细讲解
如何判断mybatis 开启二级缓存 和二级缓存详细讲解
381 0
|
网络安全 数据库 数据安全/隐私保护
docker安装Neo4j Community Server
docker安装Neo4j Community Server
1735 0
docker安装Neo4j Community Server
|
6月前
|
消息中间件 人工智能 API
100行代码讲透MCP原理
本文通过100行代码看到MCP的核心原理并不复杂,但它的设计巧妙深入理解使我们能够超越简单的SDK使用,创建更强大、更灵活的AI应用集成方案。
1223 61
100行代码讲透MCP原理
|
7月前
|
人工智能 弹性计算 自然语言处理
5分钟部署,解锁100种和AI大模型的交互可能
在AI技术飞速发展的今天,个人大模型的部署与应用面临复杂流程和高门槛。阿里云推出高效、易用的个人AI大模型部署方案,支持多模型集成、灵活扩展和定制化主页,帮助用户快速搭建专属AI主页,实现智能化新体验,真正把“AI玩出花”。
|
8月前
|
人工智能 自然语言处理 API
销售易NeoCRM与Salesforce:优势特色大比拼
本文对比了销售易NeoCRM与Salesforce两款CRM系统。销售易NeoCRM功能涵盖销售、客户、营销管理等,具AI赋能和移动办公优势,界面现代化,价格灵活适合中小企业;Salesforce功能全面,AI平台强大,生态系统丰富,全球化支持出色,适合大型及跨国企业。两者各有优劣,企业应根据自身需求选择合适的CRM系统,以实现高效管理和业务增长。
|
关系型数据库 MySQL 数据库
MySQL数据库——触发器-案例(Insert类型、Update类型和Delete类型)
MySQL数据库——触发器-案例(Insert类型、Update类型和Delete类型)
397 0
|
存储 关系型数据库 MySQL
【Java面试题汇总】MySQL数据库篇(2023版)
聚簇索引和非聚簇索引、索引的底层数据结构、B树和B+树、MySQL为什么不用红黑树而用B+树、数据库引擎有哪些、InnoDB的MVCC、乐观锁和悲观锁、ACID、事务隔离级别、MySQL主从同步、MySQL调优
【Java面试题汇总】MySQL数据库篇(2023版)
|
监控 安全 网络安全
构建安全防线:云计算环境下的网络安全策略与实践
【4月更文挑战第25天】随着企业数字化转型的深入,云计算已成为支撑现代业务架构的关键平台。然而,云服务的广泛采用同时带来了前所未有的安全挑战。本文针对云计算环境中的网络安全问题进行探讨,分析了云服务模型中存在的安全风险,并提出了一系列切实可行的安全策略和措施。这些策略不仅涵盖了数据加密、访问控制、入侵检测等传统安全领域,还包括了合规性评估、安全态势感知、以及应急响应机制等新兴话题。通过综合运用这些策略,旨在帮助组织在享受云计算带来的便利和灵活性的同时,有效防范潜在的网络威胁,确保信息安全。
164 3
|
分布式计算 网络协议 大数据
基于C++的分布式计算框架设计与实现
基于C++的分布式计算框架设计与实现
938 2
|
存储 缓存 算法
分布式Session共享解决方案
分布式Session共享解决方案
151 0