前言

给定一个长度为 n 的整数数组 nums求其中满足「相邻元素均不同」的子数组的数量。话说回来，

子数组的总数是 n·/2但我们只关心「交替子数组」——即每对相邻数字都不相同的子数组。

思路 & 痛点分析

交替数组的定义

交替数组：相邻的两个数字必须不同。形式化地，若 a 为交替数组，则对所有 k∈ 都满足 a ≠ a.

关键观察

• If a ≠ a。那么以位置 i 为的所有交替子数组都是：
  1. a
  2. a,a
  3. a,a,a
  …直到遇到第一个与前一个元素相等的位置为止。
• If a = a,那么只能形成单独的子数组 ].
• The length of longest alternating suffix ending at i,denote it by dpprefix。satisfies \=\begin{cases} dpprefix+1,& a eq a\\ 1,& a=a \end{cases} \] The total answer is sum of all se lengths.

解题过程

状态定义与转移方程

let n = nums.length;let altLen = new Array.fill;// altLen = longest alternating suffix ending at i
let ans = 0;说起来，for {
if {
altLen = + 1;} else {
altLen = 1;
}
ans += altLen;
}
return ans;

Pain point addressed:

• The algorithm runs in **O** time – eliminates TLE caused by repeated O checks.
• No extra nested loops → **O** extra work per element.
• The DP array stores only length of current alternating suffix,which is exactly information needed to count new subarrays.

为什么仅仅累加长度就能得到答案？

The value dpprefix counts how many distinct alternating subarrays end at index I. For example,if dpprefix=3,n subarrays ,。\ are all valid. Adding se counts for every index naturally yields total number of alternating subarrays in whole array.

代码实现

/**
* @param {number} nums
* @return {number}
*/
var countAlternatingSubarrays = function {
const n = nums.length;let prevLen = 0;
// 长度为 i‑1 时的最长交叉后缀
let total = 0;// 最终答案
for {
if {
// 与前一个不同，最长交叉后缀可以继续延伸
prevLen = prevLen + 1;} else {
// 与前一个相同，只能单独成子数组
prevLen = 1;}
total += prevLen;}
return total;}，

复杂度分析

• 时间复杂度：O  — 一次线性遍历就可以完成全部计数。
• 空间复杂度：O  — 只使用了常数级别的额外变量。按理说，

参考代码

/**
* Count all alternating subarrays in `nums`.
* An alternating subarray means every pair of adjacent numbers are different.
*
* @param {number} nums
* @return {number}
*/
var countAlternatingSubarrays = function {
const n = nums.length;let curLen = 0;// 当前以 i 为的最长交叉后缀长度
let answer = 0;
for {
// 若当前元素与前一个不同，则可以把之前的交叉后缀继续
if ]) {
curLen += 1;} else {
// 与前一个相同，只能形成单独的长度为 1 的子数组
curLen = 1;}
// 所有以 i 为右端点的交替子数组数量正好等于 curLen
answer += curLen;}
return answer;


};