给定长度为 n 的数组,需要统计所有元素互不相同的非空子数组数量。 核心做法是双指针滑动窗口 + 计数:
l、r 表示当前窗口 [l, r],并维护每个数在窗口中的出现次数(可用数组或哈希表,因数据范围 1 ≤ a[i] ≤ n,用数组更高效)。r 逐步右移并加入元素;如果某个元素出现次数变为 2(产生重复),就不断移动左指针 l 并减少对应计数,直到窗口内再次全为互异元素。r 为右端时,所有满足条件且以 r 结尾的子数组个数正是窗口长度 r - l + 1,累加到答案即可。在一个彩色序列中,如果一个连续的非空子序列内所有颜色互不相同,则称该子序列为一个“彩虹段”。
给定一个长度为 n 的序列 c1,c2,…,cn,每个 ci 是一个表示颜色的整数。请你计算整个序列中彩虹段的总个数。
数据范围:序列长度 n 满足 1≤n≤2×105,所有颜色值 ci 满足 1≤ci≤n。
第一行包含一个整数 n,表示序列的长度。
Scan the QR code below with WeChat to sign in
First-time scan will create your account automatically
请使用微信扫描下方二维码完成注册