3101.交替子数组计数

【LetMeFly】3101.交替子数组计数：等差数列求和（较详题解）

力扣题目链接：https://leetcode.cn/problems/count-alternating-subarrays/

给你一个二进制数组 nums 。

如果一个子数组中 不存在 两个 相邻 元素的值 相同 的情况，我们称这样的子数组为 交替子数组 。

返回数组 nums 中交替子数组的数量。

 

示例 1：

输入： nums = [0,1,1,1]

输出： 5

解释：

以下子数组是交替子数组：[0] 、[1] 、[1] 、[1] 以及 [0,1] 。

示例 2：

输入： nums = [1,0,1,0]

输出： 10

解释：

数组的每个子数组都是交替子数组。可以统计在内的子数组共有 10 个。

 

提示：

• 1 <= nums.length <= 105
• nums[i] 不是 0 就是 1 。

解题方法：等差数列求和

首先需要能看懂：

1. 若相邻两个元素不相同，则这两个元素必定不能在一个交替子数组中。
2. 若从l到r的相邻元素都不同，则l到r的任一子数组都是交替子数组。

因此任务明确了。只需要将原始数组划分为若干个最长交替子数组的集合：

例如数组[0, 1, 0, 0, 0, 1]是由三个最长交替子数组组成，

[0, 1, 0, 0, 0, 1] = [0, 1, 0] + [0] + [0, 1]。

这样就只剩下最后一个问题：对于长度为length的(最长交替子)数组，一共有多少个子数组呢？

例如对于长度为4的数组[0, 1, 0, 1]，其下标为[0, 1, 2, 3]，其子数组分别为：

• 从0到0、从0到1、从0到2、从0到3，共计4个；
• 从1到1、从1到2、从1到3，共计3个；
• 从2到2、从2到3，共计2个；
• 从3到3，共计1个。

子数组个数总计1 + 2 + 3 + 4个。

长度为length的数组一共有$1+2+\cdots+length=\frac{(1 + length) \times length}{2}$个子数组。

至此，问题解决。

• 时间复杂度$O(len(nums))$
• 空间复杂度$O(1)$

AC代码

同步发文于CSDN和我的个人博客，原创不易，转载经作者同意后请附上原文链接哦~

Tisfy：https://letmefly.blog.csdn.net/article/details/140226055