统计同值子数组的数目问题（进阶版） 题目描述 给定一个整数数组 nums ，我们需要统计所有值相同的连续子数组的数目。但是，这个进阶版本增加了一个约束：只有当子数组的长度至少为 L 且至多为 R 时，我们才对其进行计数。也就是说，我们需要找出数组中所有由相同元素组成的连续子数组，并且这些子数组的长度在 [L, R] 的闭区间内。 例如，对于数组 nums = [1, 1, 2, 2, 2, 1] ，以及 L=2 , R=3 ： 子数组 [1, 1] (索引 0-1) 长度为2，符合条件。 子数组 [2, 2, 2] (索引 2-4) 长度为3，符合条件。 子数组 [2, 2] (索引 2-3 或 3-4) 长度虽然为2，但其本身是更长同值子数组 [2,2,2] 的一部分。我们需要考虑的是不重叠的计数方式，或者所有可能的连续同值子数组？题目通常要求所有可能的连续同值子数组，只要长度在范围内。所以索引2-3和3-4这两个长度为2的子数组也符合条件。 最终结果应为 1 (对于’1’) + 1 (对于’2,2,2’) + 2 (对于’2,2’的两种取法) = 4? 不，让我们重新思考。实际上，对于一个连续出现 k 次的相同数字，它内部包含的连续同值子数组数目是 k*(k+1)/2 个（所有可能的连续子数组）。但本题有长度限制 [L, R] 。所以我们需要计算的是，对于一个连续段长度为 k 的序列，有多少个连续子数组的长度在 L 到 R 之间。 解题过程 这个问题可以通过一种高效的线性扫描方法来解决，结合简单的数学计算，而不一定需要典型的区间DP二维表。但为了符合“区间动态规划”的主题，我们可以先理解如何用区间思维来划分问题，然后优化到线性解法。 问题分析与转化 核心思路是：数组会被其内部值不同的位置自然分割成若干个连续的“同值区间”。例如 [1,1,2,2,2,1] 被分割成三个区间： [1,1] (长度2), [2,2,2] (长度3), [1] (长度1)。 我们的目标从“统计整个数组的合格子数组”转化为“分别统计每个同值区间内部的合格子数组，然后求和”。 关键子问题：单个同值区间的计算 对于一个由相同元素组成的连续段，其长度为 k 。这个连续段内部有多少个连续的子数组，其长度 len 满足 L <= len <= R ？ 一个长度为 k 的连续段，其包含的连续子数组总数是 1 + 2 + ... + k = k*(k+1)/2 （即所有可能的起点和终点组合）。 但是，我们只需要长度在 [L, R] 之间的子数组。 我们可以计算所有长度至少为 L 的子数组数目，然后减去所有长度大于 R 的子数组数目。 计算长度为 k 的连续段中，长度在 [L, R] 的子数组数目 设函数 countSegments(k, L, R) 用于计算这个值。 方法一：直接累加 对于子数组长度 len 从 L 到 min(k, R) ： 对于某个固定的长度 len ，在一个长度为 k 的序列中，有多少个连续子数组的长度恰好是 len ？答案是 k - len + 1 。 所以总数为： Σ (k - len + 1) ，其中 len 从 L 到 min(k, R) 。 即： (k - L + 1) + (k - L) + ... + (k - min(k, R) + 1) 。 这是一个等差数列求和。项数 n = min(k, R) - L + 1 。 首项 a1 = k - L + 1 ，末项 an = k - min(k, R) + 1 。 总和 S = n * (a1 + an) / 2 。 方法二：利用前缀和思想（更简洁） 长度至少为 L 的子数组数目：如果 k < L ，则为0。否则，对于长度至少为 L 的子数组，其起始索引 i 可以从0到 k-L 。对于每个起始索引 i ，对应的子数组长度可以从 L 到 k-i 。但更简单的想法是：所有长度 >= L 的子数组数量，等于所有可能的起点和终点组合中，满足“终点索引 - 起点索引 + 1 >= L”的数量。这等价于计算起点 i 和终点 j 满足 j - i >= L - 1 的数量。一个更直观的计算方法是：总子数组数（ k*(k+1)/2 ）减去长度小于 L 的子数组数（即长度为1到L-1的子数组数）。 设 F(x) 表示长度为 x 的序列的所有连续子数组的个数，即 x*(x+1)/2 。 那么，长度在 [L, R] 的子数组数目可以表示为： count = F(k) - F(L-1) - (F(k) - F(R)) 的某种组合？需要仔细推导。 更标准的计算： 长度 <= R 的子数组数： F(min(k, R)) ? 不准确。 实际上，计算长度在 [L, R] 的子数组数，可以这样： count = (长度 >= L 的子数组数) - (长度 >= R+1 的子数组数) 如何计算长度 >= X 的子数组数？ 对于一个长度为 k 的序列，长度至少为 X 的连续子数组数量是多少？ 如果 X > k ，则为0。 如果 X <= k ，那么子数组的长度可以是 X, X+1, ..., k 。 对于长度为 len 的子数组，有 k - len + 1 个。 所以总数为： Σ_{len=X}^{k} (k - len + 1) 令 t = len ，则求和为 Σ_{t=X}^{k} (k - t + 1) 。 令 j = k - t + 1 ，当 t=X 时， j = k - X + 1 ；当 t=k 时， j=1 。所以求和是 Σ_{j=1}^{k-X+1} j 。 这是一个从1到 (k - X + 1) 的求和，即 (k - X + 1) * (k - X + 2) / 2 。 因此： count_ge_L = (k - L + 1) * (k - L + 2) / 2 (如果 k >= L ，否则为0) count_ge_Rplus1 = (k - (R+1) + 1) * (k - (R+1) + 2) / 2 = (k - R) * (k - R + 1) / 2 (如果 k >= R+1 ，否则为0) 所以，最终 countSegments(k, L, R) = count_ge_L - count_ge_Rplus1 。 如果 k < L ，结果为0。 如果 L <= k <= R ，则 count_ge_Rplus1 为0（因为 k < R+1 ），结果为 count_ge_L 。 如果 k > R ，则结果为 count_ge_L - count_ge_Rplus1 。 整体算法流程（线性扫描） 初始化总计数器 total_count = 0 。 遍历数组 nums ，使用双指针或单指针扫描连续的同值段。 设置指针 i = 0 。 While i < n : 记录当前值 current_value = nums[i] 。 设置指针 j = i ，然后让 j 向后移动，直到 nums[j] != current_value 或 j 超出数组范围。此时，连续同值段的长度为 k = j - i 。 计算这个连续段中对总答案的贡献： segment_count = countSegments(k, L, R) 。 将 segment_count 加到 total_count 上。 将指针 i 更新为 j （移动到下一个不同值的开始）。 返回 total_count 。 复杂度分析 时间复杂度：O(n)，我们只遍历了数组一次，每个元素被访问一次。 空间复杂度：O(1)，只使用了常数级别的额外空间。 举例说明 回到最初的例子： nums = [1, 1, 2, 2, 2, 1] , L=2 , R=3 。 第一个连续段：值 1 ，长度 k=2 。 count_ge_L = (2-2+1)*(2-2+2)/2 = (1*2)/2 = 1 k=2 <= R=3 ，所以 count_ge_Rplus1 为0。 segment_count = 1 - 0 = 1 。 （对应子数组 [1,1] ） 第二个连续段：值 2 ，长度 k=3 。 count_ge_L = (3-2+1)*(3-2+2)/2 = (2*3)/2 = 3 count_ge_Rplus1 = (3-3)*(3-3+1)/2 = (0*1)/2 = 0 (因为 k=3 不大于 R=3 ，严格来说 k=3 并不大于 R=3 ，所以 k >= R+1 不成立，因此 count_ge_Rplus1 取0)。 segment_count = 3 - 0 = 3 。 （对应子数组 [2,2] （两种取法：索引2-3和3-4）和 [2,2,2] （一种取法：索引2-4），共3个。） 第三个连续段：值 1 ，长度 k=1 。 k=1 < L=2 ，所以 segment_count = 0 。 总数为 1 + 3 + 0 = 4 。 这个结果与之前的手动分析一致。通过将问题分解为独立的同值区间，并利用数学公式快速计算每个区间的贡献，我们高效地解决了这个进阶版的统计问题。