数组

副标题 / 摘要 除自身以外数组的乘积是典型的前后缀乘积题：不使用除法，在 O(n) 时间内完成。本文按 ACERS 结构拆解题意与算法，并给出工程迁移场景与多语言实现。 预计阅读时长：10~12 分钟 标签：Hot100、数组、前缀乘积 SEO 关键词：Product of Array Except Self, 除自身以外数组的乘积, 前缀乘积, 后缀乘积, O(n) 元描述：用前后缀乘积在 O(n) 时间内解决除自身以外数组的乘积问题，含工程场景与多语言代码。 目标读者 正在刷 Hot100 的学习者 想掌握“前后缀乘积”模型的中级开发者 需要做序列因子组合与乘积聚合的工程师 背景 / 动机 很多业务需要“排除自身的整体乘积”： 例如组合指标、冗余度评估、批量权重计算等。 若直接对每个位置做一次全数组相乘，复杂度会退化为 O(n^2)； 而题目还明确禁止使用除法，因此必须依赖前后缀乘积的线性解法。 核心概念 前缀乘积：prefix[i] = nums[0] * ... * nums[i-1] 后缀乘积：suffix[i] = nums[i+1] * ... * nums[n-1] 无除法：只允许乘法与遍历 空间优化：用结果数组承载前缀，再用后缀补乘 A — Algorithm（题目与算法） 题目还原 给定一个整数数组 nums，返回数组 answer， 其中 answer[i] 等于 nums 中除了 nums[i] 之外其余各元素的乘积。 题目保证任意元素的前缀/后缀乘积都在 32 位整数范围内。 要求：不使用除法，并在 O(n) 时间内完成。 ...

副标题 / 摘要 轮转数组是典型的数组变换题：把数组整体向右移动 k 位。本文用 ACERS 拆解“三次反转”的核心思路，并给出工程场景迁移与多语言可运行实现。 预计阅读时长：10~12 分钟 标签：Hot100、数组、旋转 SEO 关键词：Rotate Array, 轮转数组, 数组旋转, 反转, O(n) 元描述：三次反转法解决轮转数组，含复杂度对比、工程场景与多语言代码。 目标读者 正在刷 Hot100 的学习者 想掌握“数组原地变换”模板的中级开发者 需要处理时间序列对齐、轮值偏移的工程师 背景 / 动机 轮转数组在工程中非常常见： 轮值排班、时间序列对齐、环形缓冲区、前端轮播等都可以抽象为“整体右移 k 位”。 如果用逐步移动会变成 O(nk)，在数据量稍大时就不可用，因此需要更高效的原地方案。 核心概念 轮转（rotate）：把数组向右移动 k 位，后 k 个元素移到最前 k 取模：k %= n，避免 k 超过数组长度 反转（reverse）：用双指针交换来原地反转区间 原地（in-place）：在原数组上操作，额外空间 O(1) A — Algorithm（题目与算法） 题目还原 给定一个整数数组 nums，将数组中的元素向右轮转 k 个位置，其中 k 是非负数。 输入输出 名称 类型 描述 nums int[] 整数数组 k int 向右轮转步数 返回 int[] 轮转后的数组 示例 1（官方） 输入: nums = [1,2,3,4,5,6,7], k = 3 输出: [5,6,7,1,2,3,4] 示例 2（官方） 输入: nums = [-1,-100,3,99], k = 2 输出: [3,99,-1,-100] C — Concepts（核心思想） 关键思路：三次反转 反转整个数组 反转前 k 个 反转后 n-k 个 反转后的位置关系刚好等价于右移 k 位。 ...

题目要求 给定 n 个非负整数 height。每个整数表示一根宽度为 1 的柱子高度，所有柱子从左到右相邻排列。 下雨后，有些较矮的柱子上方会被两侧较高的柱子围住水。返回整张高度图最终能接住的雨水总量。 LeetCode 要求实现： class Solution: def trap(self, height: List[int]) -> int: ... 示例 1 输入：height = [0,1,0,2,1,0,1,3,2,1,2,1] 输出：6 示例 2 输入：height = [4,2,0,3,2,5] 输出：9 约束 n == len(height) 1 <= n <= 2 * 10^4 0 <= height[i] <= 10^5 Step 1：先回答一个位置能接多少水 先不计算整张高度图，只看一个位置： height = [3,0,2] ^ i = 1 下标 1 的柱子高度是 0。它左边有高度为 3 的柱子，右边有高度为 2 的柱子。 如果只看左边，似乎可以把水加到高度 3。但右边的墙只有高度 2，超过 2 的水会从右边流走。因此这个位置的水面最高只能到： min(左侧最高柱子, 右侧最高柱子) = min(3, 2) = 2 这个位置上方的水量是： ...

副标题 / 摘要 固定间距 1 检测是典型的“事件间距校验”模型。本文按 ACERS 结构拆解题意、原理与工程迁移，并给出多语言可运行实现。 预计阅读时长：10~12 分钟 标签：数组、双指针、事件间距 SEO 关键词：固定间距 1 检测, 事件间距, LeetCode 1437, O(n) 元描述：一次扫描判断所有 1 是否至少相隔 k 个位置，含工程场景、复杂度对比与多语言代码。 目标读者 刷 LeetCode 并希望沉淀“模板题”的学习者 做监控/风控/行为分析的工程师 需要判断事件间隔是否合规的系统开发者 背景 / 动机 许多系统都有“事件不能过密”的约束：例如登录失败、报警事件、敏感操作、API 调用等。 这类问题的本质是 “事件间距是否满足阈值”，与该题完全等价。 如果能用 O(n) 一次扫描完成校验，就能直接迁移到实时系统。 核心概念 事件间距：两个事件之间至少有 k 个“空位” 在线校验：只记住上一次事件的位置即可 边界处理：初始化 last = -k-1，消除首个事件特判 A — Algorithm（题目与算法） 题目还原 给定整数数组 nums 与整数 k，若任意两个 1 之间至少有 k 个 0（等价于两次 1 的索引差 > k），返回 true，否则返回 false。 输入输出 名称 类型 描述 nums int[] 仅包含 0/1 的数组 k int 需要的最小间隔 返回 bool 是否满足间距约束 示例 1 nums = [1,0,0,0,1,0,0,1], k = 2 输出: true 示例 2 nums = [1,0,1], k = 2 输出: false C — Concepts（核心思想） 关键观察 只需要记住 上一个 1 的索引 last 当遇到新的 1：若 i - last <= k，说明间隔不足 否则更新 last = i 方法归类 单次线性扫描（One-pass Scan） 事件间距校验（Event Spacing Check） 双指针 / 贪心（Greedy with last pointer） 数学表达 若 i 和 j 是两个 1 的索引（i < j），要求： ...

题目要求 给你一个整数数组 nums 和一个整数 k。一个恰好包含 k 个连续元素的窗口从 nums 最左端开始，每次向右移动一位。请按窗口从左到右的顺序，返回每个窗口中 的最大值。 窗口中的元素必须连续，其原有顺序和位置不会改变，相邻窗口可以重叠。数组中的值 可以重复，也可以是负数。 LeetCode 接口约定 LeetCode 会调用 maxSlidingWindow(nums, k)。该方法接收整数数组和一个合法的窗口 大小，返回一个整数数组，其中依次包含每个完整窗口的最大值。输入保证满足下面的 约束。 示例 示例 1： 输入：nums = [1,3,-1,-3,5,3,6,7], k = 3 输出：[3,3,5,5,6,7] 示例 2： 输入：nums = [1], k = 1 输出：[1] 约束 1 <= nums.length <= 10^5 -10^4 <= nums[i] <= 10^4 1 <= k <= nums.length 第 1 步：窗口什么时候才完整？ 在示例 1 中，当窗口右端到达索引 2 时，窗口由哪些索引组成？右端继续到达索引 3 时，又会发生什么变化？ 目前我们只知道一个大小为 k 的窗口会向右移动。要枚举所有输出时，这个描述还 不够：它既没有准确说明窗口的左端，也没有说明第一个完整窗口会在哪个位置出现。 使用从零开始的索引，把当前结束位置记为 right。如果窗口从 left 开始，并且 恰好包含 k 个元素，那么： ...

副标题 / 摘要 这是“数据结构基础”系列第 2 题：好数对计数。通过“频次统计 + 组合计数”，把 O(n^2) 直接降到 O(n)，并给出可直接迁移到工程的实现方式。 预计阅读时长：8~10 分钟 标签：哈希表、计数、数组 SEO 关键词：Good Pairs, 好数对, hash map, frequency, 计数 元描述：好数对计数的哈希表解法与工程化应用，含复杂度分析与多语言代码。 目标读者 刚开始学习哈希表与计数思想的初学者 希望把刷题方法迁移到业务统计的中级工程师 准备面试，想掌握基础计数模型的同学 背景 / 动机 “找出相同元素的两两组合数量”是一个常见的计数类问题。 在数据去重、行为分析、错误归因等场景里，这类问题通常会被反复遇到。 若用双重循环计算，复杂度是 O(n^2)；一旦数据规模扩大就会变慢。 因此需要一个可线性扩展的方案。 A — Algorithm（题目与算法） 题目还原 给你一个整数数组 nums。 如果一组数字 (i, j) 满足 nums[i] == nums[j] 且 i < j，就称为一个 好数对。 返回好数对的数目。 输入输出 名称 类型 描述 nums int[] 整数数组 返回 int 好数对数量 基础示例 nums 输出 说明 [1, 2, 3, 1, 1, 3] 4 (0,3) (0,4) (3,4) (2,5) [1, 1, 1, 1] 6 C(4,2) = 6 [1, 2, 3] 0 无重复 直观图示（示例 1） ...

副标题 / 摘要 Two Sum（两数之和）是最经典的数组哈希题：用“补数 + 哈希表”把 O(n^2) 降到 O(n)。本文按 ACERS 结构拆解题意、原理与工程迁移，并给出多语言可运行实现。 预计阅读时长：10~12 分钟 标签：Hot100、哈希表、数组、补数、面试高频 SEO 关键词：Two Sum, 两数之和, hash map, 补数, O(n), LeetCode 1, Hot100 元描述：两数之和的哈希表解法与工程应用解析，含复杂度对比与多语言代码。 目标读者 刚开始刷题，希望建立“补数 + 哈希表”基本模型的初学者 需要把算法思路迁移到工程问题的中级开发者 准备面试、想快速掌握高频题的求职者 背景 / 动机 “在一堆数字里找出两数之和”等价于一个快速配对问题，常见于对账、预算、风控、推荐等场景。 朴素暴力法虽然简单，但在数据量上来后会直接超时；哈希表一遍扫描能把复杂度从 O(n^2) 降到 O(n)，是最工程可行的做法之一。 A — Algorithm（题目与算法） 题目还原 给定一个整数数组 nums 和一个整数目标值 target，请在该数组中找出和为目标值的 两个 整数，并返回它们的数组下标。 每种输入只会对应一个答案，并且你不能使用两次相同的元素。答案可以按任意顺序返回。 输入输出 名称 类型 描述 nums int[] 整数数组 target int 目标和 返回 int[] 满足 nums[i] + nums[j] == target 的下标 基础示例 nums target 输出 [2, 7, 11, 15] 9 [0, 1] [3, 2, 4] 6 [1, 2] 补数图示（示例 1） ...

副标题 / 摘要 一道典型的“乘积 ≥ 阈值”计数题，看起来像是 O(n²) 的双重循环，实际上用「排序 + 二分查找」就能把复杂度压到 O((n+m)log m)。本文从题意抽象、核心公式到多语言实现，带你把这类阈值匹配问题彻底吃透。 预计阅读时长：10~15 分钟 适用场景标签：二分查找、排序计数、阈值匹配 SEO 关键词：spells and potions, successful pairs, 二分查找, lower_bound, 乘积约束 目标读者与背景 目标读者 已熟悉基本二分查找，想提升「在有序数组上做计数」能力的同学 后端 / 算法工程师，经常处理阈值判断与配对统计的问题 准备技术面试，希望积累“排序 + 二分”模板的开发者 为什么这题值得单独写一篇？ 它把一个表面 O(n²) 的「所有配对」问题，转化成了对有序数组的二分计数； 公式非常典型：把 a * b ≥ success 转成 b ≥ ceil(success / a)； 这种思路在推荐系统、风控额度、资源匹配等业务里屡见不鲜。 A — Algorithm（题目与算法） 题目重述 给定两个整数数组 spells 和 potions，以及一个正整数 success。 对于每个咒语 spells[i]，我们定义它与药水 potions[j] 的组合是“成功”的，当且仅当： spells[i] * potions[j] >= success 请返回一个数组 ans，其中 ans[i] 表示第 i 个咒语可以与多少个药水形成成功组合。 ...

副标题 / 摘要 一道看似麻烦的子数组题：长度必须固定为 k，元素种类又要至少 m 个，还要在满足约束下让子数组和最大。本文通过「固定窗口滑动 + 计数哈希表」，构造 O(n) 级别的简洁算法，并给出多语言实现与工程实践案例。 预计阅读时长：12~15 分钟 适用场景标签：滑动窗口进阶、distinct 计数、子数组最大和 SEO 关键词：almost unique subarray, at least m distinct, sliding window, subarray max sum 目标读者与背景 目标读者 已经掌握基础滑动窗口（如「最长无重复子串」）的刷题同学 后端 / 数据分析工程师，需要在数组或数据流上做实时统计 准备中高级面试，希望写出更工程化解法的开发者 问题背景 / 动机 许多业务都有类似需求： 推荐系统：固定长度的推荐位里，既要保证足够多的不同品类，又希望整体评分尽量高； 监控系统：在最近的固定时间窗口里，要求至少有 m 个不同指标处于活跃状态； 行为分析：在 k 次连续行为中，至少访问 m 个不同页面，且总价值最大。 本题正是这类需求的抽象版，非常适合用来练习滑动窗口 + 计数哈希表的组合技。 A — Algorithm（题目与算法） 题目重述 给定整数数组 nums，正整数 m 和 k。 如果一个长度为 k 的子数组中至少包含 m 个不同的元素，则称其为“几乎唯一子数组（almost unique subarray）”。 请在所有几乎唯一子数组中，找到元素和的最大值；如果不存在这样的子数组，则返回 0。 输入 ...