• 博客主页：音符犹如代码
• 系列专栏：算法练习
• 关注博主，后期持续更新系列文章
• 如果有错误感谢请大家批评指出，及时修改
• 感谢大家点赞👍收藏⭐评论✍

 

 

目录

思路

解题方法

时间复杂度

空间复杂度

Code 

---

思路

主要是基于对题目要求的理解和对数组遍历的应用。题目要求计算数组中所有可能的交替子数组的数量，其中交替子数组是指相邻元素不相等的子数组。

解题方法

1. 初始化：设置两个变量，ans 用于记录所有交替子数组的总数，cnt 用于记录以当前元素结尾的交替子数组的数量。由于每个元素自身至少可以构成一个交替子数组（即使它与前一个元素相同），因此 cnt 初始化为 1。

2. 遍历数组：从数组的第二个元素开始遍历（因为第一个元素自身就是一个交替子数组，无需比较）。对于每个元素，检查它是否与前一个元素不同。

   • 如果不同，说明可以将前一个交替子数组扩展一个当前元素来形成新的交替子数组，因此 cnt 递增。
   • 如果相同，说明无法将前一个交替子数组扩展，因此 cnt 重置为 1，表示当前元素自身构成一个交替子数组。

3. 累加结果：在每次迭代中，将 cnt 的值加到 ans 上，因为 cnt 表示了以当前元素结尾的所有交替子数组的数量。

4. 返回结果：遍历完成后，ans 中存储的就是所有交替子数组的总数，将其返回。

时间复杂度 

时间复杂度是 O(n)，其中 n 是数组 nums 的长度。因为我们只需要遍历一次数组即可完成计算，所以时间复杂度与数组的长度成正比。

空间复杂度

空间复杂度是 O(1)。尽管我们使用了几个变量（ans、cnt 和循环变量 i），但这些变量的数量是固定的，不随输入数组的大小而增加。因此，我们可以认为算法使用的额外空间是常数级别的，即空间复杂度为 O(1)。

Code

class Solution {  
    public long countAlternatingSubarrays(int[] nums) {  
        long ans = 0; // 用于累积交替子数组的总数  
        int cnt = 1;  // 以当前元素结尾的交替子数组的数量（初始化为1，因为每个元素自身都是一个交替子数组）  
        for (int i = 0; i < nums.length; i++) {  
            // 如果当前元素与前一个元素不同，则增加以当前元素结尾的交替子数组数量  
            if (i > 0 && nums[i] != nums[i - 1]) {  
                cnt++;  
            } else {  
                // 如果当前元素与前一个元素相同，则重置以当前元素结尾的交替子数组数量为1  
                cnt = 1;  
            }  
            // 将以当前元素结尾的交替子数组数量加到总数上  
            ans += cnt;  
        }  
        return ans; // 返回所有交替子数组的总数  
    }  
}

 

One today is worth two tomorrows.  Benjamin Franklin 一个今天抵得上两个明天。——本杰明弗兰克林