整数数组中符合条件的长度≥3子序列计数：高效解法探究

问题描述 #

给定一个长度为N的整数数组，需返回满足以下条件的长度至少为3的子序列数量：

• 子序列首元素与尾元素相等；
• 首尾元素的值等于子序列中间部分（排除首尾元素）的元素和；
• 禁止排序或修改数组元素顺序。

朴素解法的问题 #

你提供的朴素解法采用两层嵌套循环，时间复杂度为O(n²)。当数组规模较大（比如n=10^4）时，这种解法会因计算量过大而超时，无法高效处理大规模数据。

优化思路 #

我们可以通过条件转化+哈希表统计的方式，将时间复杂度降至O(n)：
原条件可变形为：
对于子序列的首尾索引i和j（j ≥ i+2）：

1. capacity[i] == capacity[j]
2. prefix_sum[j-1] == prefix_sum[i] + capacity[i]（其中prefix_sum是数组的前缀和数组）

核心思路是：遍历每个可能的尾索引j时，用哈希表提前记录所有符合条件的首索引i的统计信息，直接查询满足条件的i的数量，避免嵌套循环。

高效实现代码 #

from collections import defaultdict

def count_balanced_subsegments(capacity):
    n = len(capacity)
    if n < 3:
        return 0
    
    # 计算前缀和数组
    prefix_sum = [0] * n
    prefix_sum[0] = capacity[0]
    for i in range(1, n):
        prefix_sum[i] = prefix_sum[i-1] + capacity[i]
    
    count = 0
    # value_map: key是元素值v，value是{sum_key: 出现次数}，sum_key=prefix_sum[i]+capacity[i]
    value_map = defaultdict(lambda: defaultdict(int))
    # 先加入第一个元素的信息（i=0）
    first_v = capacity[0]
    first_sum_key = prefix_sum[0] + capacity[0]
    value_map[first_v][first_sum_key] += 1
    
    # 遍历所有可能的尾索引j（j从2开始，因为子序列长度至少3）
    for j in range(2, n):
        target = prefix_sum[j-1]
        current_v = capacity[j]
        # 查询有多少个i满足capacity[i]=current_v且prefix_sum[i]+capacity[i]=target
        count += value_map[current_v].get(target, 0)
        
        # 将j-1位置的信息加入哈希表，供后续的j'使用
        prev_v = capacity[j-1]
        prev_sum_key = prefix_sum[j-1] + capacity[j-1]
        value_map[prev_v][prev_sum_key] += 1
    
    return count

# 示例测试
capacity = [9, 3, 3, 3, 9]
result = count_balanced_subsegments(capacity)
print(result)  # 输出：2

代码说明 #

1. 前缀和数组：提前计算前缀和，快速得到任意区间的元素和；
2. 哈希表value_map：记录每个元素值对应的prefix_sum[i]+capacity[i]的出现次数，这样在遍历尾索引j时，能直接查询符合条件的首索引i的数量；
3. 遍历逻辑：遍历j时，先查询满足条件的i的数量，再将j-1的信息加入哈希表（因为后续的j'可以以j-1作为首索引i）。

内容的提问来源于stack exchange，提问作者Peter Bilko