企业官网建设流程全解析

• 科学计算

导读

本文基于算法竞赛模板库 codeforces-go 中 leetcode/weekly/315/d/README.md 的官方题解，深入讲解 LeetCode 第 315 场周赛 D 题（2444. 统计定界子数组的数目）的线性解法。核心方法是"从特殊到一般"：先剖析所有元素均落在[minK, maxK]内的简化模型，再引入"范围外最近元素"哨兵位置，将问题收敛为一次遍历中实时维护三个下标并累加贡献的 O(n) 算法。读完本文，你将掌握"枚举子数组右端点、统计合法左端点"这一通用贡献法套路，并能将其迁移到区间计数类问题的求解中。

一、题目与题解在仓库中的位置

本题解收录于本仓库的周赛题解目录中，对应的仓库结构如下：

• 题解文档：leetcode/weekly/315/d/README.md
• Go 参考实现：leetcode/weekly/315/d/d.go
• 单元测试：leetcode/weekly/315/d/d_test.go
• 测试用例数据：leetcode/weekly/315/d/d.txt

题意可概括为：给定整数数组nums以及下界minK、上界maxK，统计所有满足下述条件的子数组数目：

1. 子数组的最小值等于minK；
2. 子数组的最大值等于maxK。

一个朴素的做法是枚举全部 O(n²) 个子数组并逐一检查，但题目数据规模要求线性解法。原题解给出的思路正是"从特殊到一般"，这也是本篇文章展开的主线。

二、从特殊到一般：先攻克简化模型

原题解开篇即点明方法论——先考虑一个简单的情况：nums的所有元素都在[minK, maxK]范围内。在这种理想情形下，任意子数组的最小值天然不小于minK、最大值天然不大于maxK，于是原问题等价于：

同时包含minK和maxK的子数组的个数。

核心思路：枚举右端点，统计合法左端点

遍历nums，动态维护两个关键下标：

• minI：minK最近一次出现的位置；
• maxI：maxK最近一次出现的位置。

当遍历到nums[i]时，如果minK和maxK都曾出现过，则所有左端点落在[0, min(minI, maxI)]的子数组都同时包含minK与maxK。这是因为：

• 右端点固定为i；
• 只要左端点不超过min(minI, maxI)，区间[left, i]就必然覆盖了最近的那个minK和最近的那个maxK；
• 由于所有元素都在范围内，同时包含minK和maxK的子数组，其最小值一定是minK、最大值一定是maxK。

因此，以i为右端点的合法子数组个数为：

$$ \min(\textit{minI},\textit{maxI})+1 $$

把每个右端点对应的贡献累加起来，就是简化模型的答案。

手动推演一个例子

以题解给出的图解数据nums = [1, 4, 3, 4, 2, 2, 3, 3]（对应minK = 2, maxK = 4）为例，前四个元素中4出现两次（下标 1、3），minK = 2到下标 4 才首次出现：

• 遍历到i = 4（值2）时，minI = 4、maxI = 3，贡献min(4, 3) + 1 = 4，即左端点可取0..3；
• 遍历到i = 5（值2）时，minI = 5、maxI = 3，贡献min(5, 3) + 1 = 4；
• 遍历到i = 6（值3）时，minI = 5、maxI = 6，贡献min(5, 6) + 1 = 6，左端点可取0..5。

注意：元素1位于[2, 4]之外，属于"越界元素"，因此在一般模型中需要额外处理（见下一节）。

三、回到原问题：引入范围外哨兵i0

真实数据中，nums必然存在落在[minK, maxK]之外的元素，而合法子数组不能包含任何越界元素。若不做处理，上面的计数会把跨过越界元素的子数组也算进去，造成多算。

原题解的解法是：额外维护一个下标

• i0：在[minK, maxK]范围之外的最近元素位置。

有了i0之后，以i为右端点时，左端点必须在i0右侧，即左端点取值范围收缩为：

$$ [\textit{i}_0+1,\ \min(\textit{minI},\textit{maxI})] $$

于是一般情形下以i为右端点的合法子数组个数为：

$$ \min(\textit{minI},\textit{maxI})-\textit{i}_0 $$

结合上述nums = [1, 4, 3, 4, 2, 2, 3, 3]的例子：下标0处的元素1越界，i0 = 0。则：

• i = 4时，贡献变为min(4, 3) - 0 = 3，即左端点只能取1..3，排除了越界元素1所在的子数组（左端点 0）；
• i = 6时，贡献变为min(5, 6) - 0 = 5，左端点取1..5。

可见，i0相当于一道"禁止越界"的闸门，把跨越越界元素的子数组全部排除在外。

实现时的两个工程细节

原题解特别指出代码实现时需要注意的两点：

1. 初始化哨兵为-1：令minI = maxI = i0 = -1，天然兼容"尚未找到相应元素"的情况——在minK或maxK出现之前，min(minI, maxI)为-1，min(minI, maxI) - i0为负或零，贡献不会为正。

2. 对贡献取max(..., 0)下限保护：若min(minI, maxI) - i0 < 0，说明在i0右侧minK和maxK尚未同时出现，此时以i为右端点的合法子数组个数为0。因此统一写成：

$$ \max\big(\min(\textit{minI},\textit{maxI})-\textit{i}_0,\ 0\big) $$

避免向答案累加负数。

四、多语言代码实现

原题解给出了 Python、Java、C++、C、Go、JavaScript、Rust 共七种语言的完整实现，核心逻辑完全一致（单次遍历、三个下标、O(1) 辅助空间）。以下全部原样收录，便于跨语言对比与直接复用。

class Solution: def countSubarrays(self, nums: List[int], minK: int, maxK: int) -> int: ans = 0 min_i = max_i = i0 = -1 for i, x in enumerate(nums): if x == minK: min_i = i # 最近的 minK 位置 if x == maxK: max_i = i # 最近的 maxK 位置 if not minK <= x <= maxK: i0 = i # 子数组不能包含 nums[i0] ans += max(min(min_i, max_i) - i0, 0) return ans

class Solution: def countSubarrays(self, nums: List[int], minK: int, maxK: int) -> int: ans = 0 min_i = max_i = i0 = -1 for i, x in enumerate(nums): if x == minK: min_i = i if x == maxK: max_i = i if not minK <= x <= maxK: i0 = i j = min_i if min_i < max_i else max_i if j > i0: ans += j - i0 return ans

class Solution { public long countSubarrays(int[] nums, int minK, int maxK) { long ans = 0; int minI = -1, maxI = -1, i0 = -1; for (int i = 0; i < nums.length; i++) { int x = nums[i]; if (x == minK) { minI = i; // 最近的 minK 位置 } if (x == maxK) { maxI = i; // 最近的 maxK 位置 } if (x < minK || x > maxK) { i0 = i; // 子数组不能包含 nums[i0] } ans += Math.max(Math.min(minI, maxI) - i0, 0); } return ans; } }

class Solution { public: long long countSubarrays(vector<int>& nums, int minK, int maxK) { long long ans = 0; int min_i = -1, max_i = -1, i0 = -1; for (int i = 0; i < nums.size(); i++) { int x = nums[i]; if (x == minK) { min_i = i; // 最近的 minK 位置 } if (x == maxK) { max_i = i; // 最近的 maxK 位置 } if (x < minK || x > maxK) { i0 = i; // 子数组不能包含 nums[i0] } ans += max(min(min_i, max_i) - i0, 0); } return ans; } };

#define MIN(a, b) ((b) < (a) ? (b) : (a)) #define MAX(a, b) ((b) > (a) ? (b) : (a)) long long countSubarrays(int* nums, int numsSize, int minK, int maxK) { long long ans = 0; int min_i = -1, max_i = -1, i0 = -1; for (int i = 0; i < numsSize; i++) { int x = nums[i]; if (x == minK) { min_i = i; // 最近的 minK 位置 } if (x == maxK) { max_i = i; // 最近的 maxK 位置 } if (x < minK || x > maxK) { i0 = i; // 子数组不能包含 nums[i0] } ans += MAX(MIN(min_i, max_i) - i0, 0); } return ans; }

func countSubarrays(nums []int, minK, maxK int) (ans int64) { minI, maxI, i0 := -1, -1, -1 for i, x := range nums { if x == minK { minI = i // 最近的 minK 位置 } if x == maxK { maxI = i // 最近的 maxK 位置 } if x < minK || x > maxK { i0 = i // 子数组不能包含 nums[i0] } ans += int64(max(min(minI, maxI)-i0, 0)) } return }

var countSubarrays = function(nums, minK, maxK) { let ans = 0, minI = -1, maxI = -1, i0 = -1; for (let i = 0; i < nums.length; i++) { const x = nums[i]; if (x === minK) { minI = i; // 最近的 minK 位置 } if (x === maxK) { maxI = i; // 最近的 maxK 位置 } if (x < minK || x > maxK) { i0 = i; // 子数组不能包含 nums[i0] } ans += Math.max(Math.min(minI, maxI) - i0, 0); } return ans; };

impl Solution { pub fn count_subarrays(nums: Vec<i32>, min_k: i32, max_k: i32) -> i64 { let mut ans = 0; let mut min_i = -1; let mut max_i = -1; let mut i0 = -1; for (i, x) in nums.into_iter().enumerate() { let i = i as i32; if x == min_k { min_i = i; // 最近的 min_k 位置 } if x == max_k { max_i = i; // 最近的 max_k 位置 } if x < min_k || x > max_k { i0 = i; // 子数组不能包含 nums[i0] } ans += 0.max(min_i.min(max_i) - i0) as i64; } ans } }

其中，Go 版本的写法与仓库中的参考实现完全一致；注意返回值类型为int64（Java 为long、C++ 为long long、Rust 为i64），这是为了防止大数组下答案溢出 32 位整型。

复杂度分析

• 时间复杂度：O(n)，其中 n 为nums的长度。每个元素仅被遍历一次，每次迭代只做常数次比较与加法。
• 空间复杂度：O(1)，仅使用minI、maxI、i0与ans四个变量。

五、仓库源码与测试佐证

1. Go 参考实现

仓库中的 d.go 与题解文档中的 Go 代码一一对应，同样维护minI / maxI / i0三个下标，并在循环内执行ans += int64(max(min(minI, maxI)-i0, 0))，最后通过命名返回值直接return。文件末尾还内联了min/max两个工具函数（在 Go 1.21 内置min/max之前的常见写法）。

2. 测试驱动与用例数据

该题解配套了完整的测试链路：

• d_test.go 通过testutil.RunLeetCodeFuncWithFile(t, countSubarrays, "d.txt", targetCaseNum)驱动测试，测试函数签名直接指向countSubarrays；
• 测试用例数据保存在 d.txt 中，采用"每 3 行一组"的格式（函数有 2 个输入参数 + 1 个返回值），共两组用例：
  • nums = [1,3,5,2,7,5]、minK = 1、maxK = 5→ 答案2（越界元素7把数组切分为两段，合法子数组为[1,3,5]与[1,3,5,2]）；
  • nums = [1,1,1,1]、minK = 1、maxK = 1→ 答案10（全部元素合法，任意子数组都满足条件，即 4×5/2 = 10）。

3. 测试工具的实现原理

测试框架 leetcode/testutil/leetcode.go 中的RunLeetCodeFuncWithFile会读取用例文件，按函数的参数个数 + 返回值个数（fNumIn + fNumOut）切分行数据，再反射调用被测函数并逐例断言。这意味着：只要照着题解把函数实现补全，即可通过仓库自带的用例数据一键验证正确性，也可以在此基础上自行追加用例。

六、相似题目与迁移要点

原题解末尾将本题归入"滑动窗口与双指针 / 区间计数"一类，并列出相似题目：

• 795. 区间子数组个数：统计"最大值位于[left, right]"的子数组数量，同样是利用"枚举右端点、维护边界下标、累加左端点个数"的套路，与本题的i0闸门思想同源。

这一类题目的通用迁移要点可以总结为：

1. 先化简再还原：先假设数据无干扰，建立计数公式；再引入"非法元素最近位置"作为哨兵，把公式修正到真实数据上；
2. 枚举右端点、统计左端点：把"数子数组"转化为"对每个右端点，求合法左端点区间长度"，避免 O(n²) 枚举；
3. 哨兵初值-1+ 贡献下限max(..., 0)：保证未出现所需元素时不产生负贡献，是代码可读性与正确性的关键。

七、小结

本文完整复现了 leetcode/weekly/315/d/README.md 的核心思路：通过"从特殊到一般"的递进推导，将"统计定界子数组"转化为单次遍历下对minI、maxI、i0三个下标的维护与贡献累加，最终得到 O(n) 时间、O(1) 空间的解法，并配套给出了七种主流语言的实现与仓库内可运行的测试链路。掌握"枚举右端点、统计合法左端点"的贡献法，即可举一反三地处理一类区间计数问题。

• 科学计算