Meta 奇偶交替子数组：以右端点计数

题意与假设

这道练习题保留了面经中值得训练的核心约束，并将需要澄清的条件单独列出。现场拿到变体时，先和面试官确认这些条件。

• 整数正负零均可；奇偶按value%2，零是偶数。子数组非空，连续且所有相邻对异奇偶。
• 同值不同位置的片段分别计数，返回总数量，不输出片段列表。

解题路线

1. length是以当前右端点结束的最长交替后缀。若新值奇偶与上一个不同，length++；否则重置为1。
2. 以当前元素结束的合法子数组分别是该后缀的最后1、2、…、length项，共length个，累加到答案。
3. 等价地将数组切为最大交替段，每段长度L贡献L(L+1)/2；在线右端累计避免保存段边界。

手动走一遍

[1,2,3,7,8,9]在3/7之间同奇切开，两段长度3各贡献6，合计12。[2,2]只有两个单元素合法，总2。

Python 参考实现

下面的代码按上文假设实现，适合本地运行并追加自己的测试用例。

代码区可横向滚动；使用键盘时，先聚焦代码区再按方向键查看。

def alternating_subarray_count(values):
    answer = length = 0
    previous = None
    for value in values:
        parity = value % 2
        length = length + 1 if previous is not None and parity != previous else 1
        answer += length
        previous = parity
    return answer

复杂度

O(n)时间，O(1)辅助空间；总数最大n(n+1)/2，固定宽度语言使用足够大的整数。

易错点与追问

容易失分的边界

• 仅统计长度>=2会遗漏题目明确包含的单元素。
• 负数不能用value>0判断奇偶，余数模型按语言规则核对。

继续深挖

• 若要求长度至少m，每个右端贡献max(0,length−m+1)。
• 若相邻条件改成值严格上升，仍可维护合法后缀长度；条件需只依赖相邻二元关系。