题目描述
给你一个二进制数组 nums
。
如果一个子数组中 不存在 两个 相邻 元素的值 相同 的情况,我们称这样的子数组为 交替子数组。
返回数组 nums
中交替子数组的数量。
样例
输入: nums = [0,1,1,1]
输出: 5
解释:
以下子数组是交替子数组:[0]、[1]、[1]、[1] 以及 [0,1]。
输入: nums = [1,0,1,0]
输出: 10
解释:
数组的每个子数组都是交替子数组。可以统计在内的子数组共有 10 个。
限制
1 <= nums.length <= 10^5
nums[i]
不是0
就是1
。
算法
(双指针) $O(n^2)$
- 对于每个以 $i$ 为结尾的位置,维护起始位置 $j$,满足区间 $[j, i]$ 是交替子数组。
- 这种情况下,区间 $[j, i], [j + 1, i], \dots, [i, i]$ 都是满足条件的交替子数组,累加答案 $i - j + 1$。
- 注意到,当 $nums(i) == nums(i - 1)$ 时,更新 $j$ 为 $i$。
时间复杂度
- 遍历数组一次,时间复杂度为 $O(n)$。
空间复杂度
- 仅需要常数的额外空间。
C++ 代码
#define LL long long
class Solution {
public:
LL countAlternatingSubarrays(vector<int>& nums) {
const int n = nums.size();
LL ans = 1;
for (int i = 1, j = 0; i < n; i++) {
if (nums[i] == nums[i - 1])
j = i;
ans += i - j + 1;
}
return ans;
}
};