LeetCode 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 <= 105nums[i]不是0就是1。
解题方法：等差数列求和
首先需要能看懂：
- 若相邻两个元素不相同，则这两个元素必定不能在一个
交替子数组中。 - 若从
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 + ⋯ + l e n g t h = ( 1 + l e n g t h ) × l e n g t h 2 1+2+\cdots+length=\frac{(1 + length) \times length}{2} 1+2+⋯+length=2(1+length)×length个子数组。
至此，问题解决。
- 时间复杂度 O ( l e n ( n u m s ) ) O(len(nums)) O(len(nums))
- 空间复杂度 O ( 1 ) O(1) O(1)
AC代码
同步发文于CSDN和我的个人博客，原创不易，转载经作者同意后请附上原文链接哦~
Tisfy：https://letmefly.blog.csdn.net/article/details/140226055