Leetcode-3101题解

leetcode 3101 题解

题目

给你一个二进制数组 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 。

思路

数学

当一个数新加入数列的时候，判断其（nums[i]）与上一个数（nums[i-1]）是否相同；还需要一个数 prev 记录上一个非交替子数列结束的下标。如果相同，则从 prev 到当前下标，除了 nums[i] 本身，均不存在交替子数列， prev 赋值为当前下标；如果不同，则从 nums[prev] 到 nums[i-1] ，均能与 nums[i] 形成交替子数列，所以会增加 prev - i 个交替子数列，加上 nums[i] 本身，一共有 prev - i + 1 个交替子数列。

注意：代码实现的时候，不要忘记 nums[0] 本身也是一个交替子数列。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

class Solution {
public:
    long long countAlternatingSubarrays(vector<int>& nums) {
        int prev = 0, n = nums.size();
        long long sum = 1;
        for (int i = 1; i < n; i++) {
            if (nums[i] != nums[i - 1]) {
                sum += i - prev + 1;
            } else {
                sum += 1;
                prev = i;
            }
        }
        return sum;
    }
};