南京市住房和城乡建设部网站,策划公司口号,网站优化与SEO区别,青岛企业网站seo技巧博客主页#xff1a;音符犹如代码系列专栏#xff1a;算法练习关注博主#xff0c;后期持续更新系列文章如果有错误感谢请大家批评指出#xff0c;及时修改感谢大家点赞#x1f44d;收藏⭐评论✍ 目录
思路
解题方法
时间复杂度
空间复杂度
Code 思路
主要是基于对…博客主页音符犹如代码系列专栏算法练习关注博主后期持续更新系列文章如果有错误感谢请大家批评指出及时修改感谢大家点赞收藏⭐评论✍ 目录
思路
解题方法
时间复杂度
空间复杂度
Code 思路
主要是基于对题目要求的理解和对数组遍历的应用。题目要求计算数组中所有可能的交替子数组的数量其中交替子数组是指相邻元素不相等的子数组。
解题方法 初始化设置两个变量ans 用于记录所有交替子数组的总数cnt 用于记录以当前元素结尾的交替子数组的数量。由于每个元素自身至少可以构成一个交替子数组即使它与前一个元素相同因此 cnt 初始化为 1。 遍历数组从数组的第二个元素开始遍历因为第一个元素自身就是一个交替子数组无需比较。对于每个元素检查它是否与前一个元素不同。 如果不同说明可以将前一个交替子数组扩展一个当前元素来形成新的交替子数组因此 cnt 递增。如果相同说明无法将前一个交替子数组扩展因此 cnt 重置为 1表示当前元素自身构成一个交替子数组。 累加结果在每次迭代中将 cnt 的值加到 ans 上因为 cnt 表示了以当前元素结尾的所有交替子数组的数量。 返回结果遍历完成后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 一个今天抵得上两个明天。——本杰明弗兰克林
