【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
