统计同值子数组的数目问题（进阶版）

让我为您讲解一个区间动态规划的进阶题目：统计同值子数组的数目问题。

题目描述

给定一个整数数组 nums 和一个整数 k，统计满足以下条件的非空连续子数组的数目：

1. 子数组中所有元素都相同
2. 子数组的长度至少为 k

例如，对于数组 [1,1,2,2,2,1] 和 k=2：

• 有效的子数组：[1,1]、[2,2]、[2,2,2]、[2,2]（第二个和第三个元素）
• 无效的子数组：单个元素 [1]、[2] 等（长度小于2）

解题思路

这个问题可以用区间动态规划结合分组思想来解决。核心思路是将连续的相同元素分组，然后在每个组内计算满足条件的子数组数目。

详细解题步骤

步骤1：预处理 - 将连续相同元素分组

首先，我们需要将数组中连续的相同元素分组存储：

• 每个组记录：元素值、连续出现的次数
• 例如：[1,1,2,2,2,1] → 分组为：[(1,2), (2,3), (1,1)]

def group_elements(nums):
    groups = []
    n = len(nums)
    i = 0
    while i < n:
        count = 1
        current = nums[i]
        while i + 1 < n and nums[i + 1] == current:
            count += 1
            i += 1
        groups.append((current, count))
        i += 1
    return groups

步骤2：定义动态规划状态

对于每个分组 (value, count)，我们定义：

• dp[i]：表示以当前分组中第 i 个元素结尾的满足条件的子数组数目
• 这里 i 指的是分组内的位置索引（从1开始）

步骤3：状态转移方程

对于长度为 count 的连续相同元素分组：

• 如果子数组长度 L 满足 k ≤ L ≤ count，那么这样的子数组有 count - L + 1 个
• 更高效的计算方法：对于位置 i（从1到count）
  • 如果 i < k：dp[i] = 0（长度不够）
  • 如果 i ≥ k：dp[i] = dp[i-1] + 1

步骤4：计算每个分组的贡献

对于每个分组 (value, count)，满足条件的子数组总数为：

sum = 0
for i from k to count:
    sum += (i - k + 1)

这可以用数学公式简化为：

如果 count < k: 贡献为 0
如果 count ≥ k: 贡献为 (count - k + 1) * (count - k + 2) // 2

步骤5：汇总所有分组的贡献

将所有分组的贡献相加，得到最终结果。

完整代码实现

def count_homogeneous_subarrays(nums, k):
    # 步骤1：分组
    groups = []
    n = len(nums)
    i = 0
    while i < n:
        count = 1
        current = nums[i]
        while i + 1 < n and nums[i + 1] == current:
            count += 1
            i += 1
        groups.append(count)
        i += 1
    
    # 步骤2：计算每个分组的贡献
    total = 0
    for count in groups:
        if count < k:
            continue
        # 计算该分组的贡献：长度为k, k+1, ..., count的子数组个数
        # 即 (count - k + 1) + (count - k) + ... + 1
        total += (count - k + 1) * (count - k + 2) // 2
    
    return total

# 示例验证
nums = [1, 1, 2, 2, 2, 1]
k = 2
result = count_homogeneous_subarrays(nums, k)
print(f"满足条件的子数组数目: {result}")  # 输出: 4

算法复杂度分析

• 时间复杂度：O(n)，其中n是数组长度。我们只需要遍历数组两次：一次分组，一次计算贡献。
• 空间复杂度：O(m)，其中m是分组数量，最坏情况下为O(n)。

进阶思考

这个问题的区间动态规划特性体现在：

1. 最优子结构：每个连续相同元素段是独立的子问题
2. 无后效性：一个段的计算结果不影响其他段
3. 重叠子问题：在计算每个段内的子数组数目时，存在重复的计算模式

这种方法比暴力枚举所有子数组的O(n²)方法要高效得多。