Medium

题目描述

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

提示：

  • 尝试使用动态规划。
  • 设 dp[i] 为以索引 i 结尾的交替子数组数量。
  • 最终答案是所有索引 i（从 0 到 n-1）的 dp[i] 之和。

解题思路

解题思路

这道题要求计算二进制数组中所有交替子数组的数量。关键是理解"交替"的含义：相邻元素值不同。

动态规划解法（推荐）

根据题目提示，我们可以用动态规划来解决：

  • 定义 dp[i] 为以位置 i 结尾的交替子数组数量
  • 状态转移：
    • 如果 nums[i] != nums[i-1]，那么 dp[i] = dp[i-1] + 1
    • 否则 dp[i] = 1（只有单个元素的子数组）

这里的核心思想是：如果当前元素与前一个元素不同，那么以当前位置结尾的交替子数组数量等于以前一个位置结尾的数量加1（因为可以将当前元素添加到之前的所有交替子数组中）。

优化空间复杂度

由于 dp[i] 只依赖于 dp[i-1]，我们可以用一个变量来记录当前连续交替序列的长度，从而将空间复杂度优化到 O(1)。

每个位置的贡献就是当前连续交替序列的长度。

代码实现

class Solution {
public:
    long long countAlternatingSubarrays(vector<int>& nums) {
        int n = nums.size();
        long long result = 0;
        int length = 1;  // 当前连续交替序列长度
        
        result += 1;  // 第一个元素自己构成的子数组
        
        for (int i = 1; i < n; i++) {
            if (nums[i] != nums[i-1]) {
                length++;
            } else {
                length = 1;
            }
            result += length;
        }
        
        return result;
    }
};

class Solution:
    def countAlternatingSubarrays(self, nums: List[int]) -> int:
        n = len(nums)
        result = 0
        length = 1  # 当前连续交替序列长度
        
        result += 1  # 第一个元素自己构成的子数组
        
        for i in range(1, n):
            if nums[i] != nums[i-1]:
                length += 1
            else:
                length = 1
            result += length
        
        return result

public class Solution {
    public long CountAlternatingSubarrays(int[] nums) {
        int n = nums.Length;
        long result = 0;
        int length = 1;  // 当前连续交替序列长度
        
        result += 1;  // 第一个元素自己构成的子数组
        
        for (int i = 1; i < n; i++) {
            if (nums[i] != nums[i-1]) {
                length++;
            } else {
                length = 1;
            }
            result += length;
        }
        
        return result;
    }
}

/**
 * @param {number[]} nums
 * @return {number}
 */
var countAlternatingSubarrays = function(nums) {
    const n = nums.length;
    let result = 0;
    let length = 1;  // 当前连续交替序列长度
    
    result += 1;  // 第一个元素自己构成的子数组
    
    for (let i = 1; i < n; i++) {
        if (nums[i] !== nums[i-1]) {
            length++;
        } else {
            length = 1;
        }
        result += length;
    }
    
    return result;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度说明
时间复杂度O(n)只需要遍历数组一次
空间复杂度O(1)只使用了常数个额外变量