子数组

副标题 / 摘要 最大子数组和是最经典的一维 DP / 贪心题。本文用 ACERS 模板拆解 Kadane 算法，给出工程迁移思路与多语言可运行实现。 预计阅读时长：10~12 分钟 标签：Hot100、动态规划、贪心 SEO 关键词：Maximum Subarray, 最大子数组和, Kadane, 动态规划, O(n) 元描述：Kadane 一维 DP 求最大子数组和，含工程场景、复杂度分析与多语言代码。 目标读者 正在刷 Hot100 的学习者 想掌握“最大子段和”经典模板的中级开发者 需要做序列区间增益分析的工程师 背景 / 动机 最大子数组和不仅是 LeetCode 经典题，也常见于实际系统： 交易收益区间、指标提升区间、日志峰值段落、吞吐提升区间等都可以抽象为“最大连续收益”。 朴素 O(n^2) 枚举无法扩展，Kadane 给出 O(n) 的线性解。 核心概念 子数组：连续且非空的数组片段 状态转移：dp[i] 表示“以 i 结尾的最大子数组和” Kadane 思想：如果前缀和为负，直接丢弃，从当前位置重新开始 A — Algorithm（题目与算法） 题目还原 给你一个整数数组 nums，找出一个具有最大和的连续子数组（子数组至少包含一个元素），返回其最大和。 输入输出 名称 类型 描述 nums int[] 整数数组 返回 int 最大子数组和 示例 1（官方） nums = [-2,1,-3,4,-1,2,1,-5,4] 输出 = 6 解释：子数组 [4,-1,2,1] 和为 6 示例 2（官方） nums = [1] 输出 = 1 C — Concepts（核心思想） 关键公式 设 dp[i] 为以 i 结尾的最大子数组和： ...

副标题 / 摘要 这是 Hot100 专栏第 1 篇：和为 K 的子数组。本文用“前缀和 + 频次哈希表”把 O(n^2) 降到 O(n)，并按 ACERS 模板给出工程场景与多语言实现。 预计阅读时长：12~15 分钟 标签：Hot100、前缀和、哈希表 SEO 关键词：Subarray Sum Equals K, 和为K的子数组, 前缀和, 哈希表, O(n) 元描述：和为 K 的子数组计数问题的前缀和解法，含工程迁移、复杂度对比与多语言代码。 目标读者 正在刷 Hot100，希望建立稳定算法模板的初学者 需要把计数类算法迁移到业务数据统计的中级工程师 准备面试，想掌握“前缀和 + 哈希表”核心套路的人 背景 / 动机 “统计和为 K 的子数组数量”是最经典的计数类问题之一。 它广泛出现在日志分析、风控阈值命中、交易序列统计等场景。 朴素的两层遍历虽然直观，但一旦数据规模增大就会明显卡顿，因此需要可扩展的 O(n) 解法。 核心概念（必须理解） 子数组：数组中连续、非空的片段 前缀和：prefix[i] = nums[0..i] 的和 差分关系：若 prefix[r] - prefix[l-1] = k，则 nums[l..r] 的和为 k 频次哈希表：统计某个前缀和出现的次数，以 O(1) 均摊时间查询 A — Algorithm（题目与算法） 题目还原 给你一个整数数组 nums 和一个整数 k，请统计并返回 和为 k 的子数组 的个数。 子数组是数组中元素的连续非空序列。 ...