题目
给你一个二进制数组（0、1组成）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 <= 10^5- nums[i] 不是 0 就是 1 。
分析
- 有效的子数组必须是连续子数组
- 单个元素可能的事有效的子数组
- 两个元素
- 对于当前位置是1的元素，往后的0元素都是可以组合的
- 对于0亦如此
- 对于三个元素亦是如此
枚举每个元素，尝试从短到长统计连续交替子数组——向后枚举累加
class Solution {
public long countAlternatingSubarrays(int[] nums) {
int count = 0;
for (int i = 0;i < nums.length;i++) {
count++;
boolean needChange = true;
for (int j = i + 1;j< nums.length;j++) {
if (needChange) {
if (nums[j] != nums[i]) {
count++;
needChange = false;
} else {
break;
}
}else {
if (nums[j] == nums[i]) {
count++;
needChange = true;
} else {
break;
}
}
}
}
return count;
}
}
向前累加
- 对于i处的元素
- 如果和i-1的元素一样，则需要从头开始计算累加数组
- 如果和i-1的元素一样，则需要+1并累加数组
class Solution {
public long countAlternatingSubarrays(int[] nums) {
long ans = 0;
int cnt = 0;
for (int i = 0; i < nums.length; i++) {
if (i > 0 && nums[i] != nums[i - 1]) {
cnt++;
} else {
cnt = 1;
}
ans += cnt; // 有 cnt 个右端点下标为 i 的交替子数组
}
return ans;
}
}
转载请注明来源，欢迎对文章中的引用来源进行考证，欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论，也可以邮件至 1056615746@qq.com
