解题思路
本题要求统计所有满足条件的下标区间个数,条件为区间内每个位置上的两个序列元素均不相同(即 xi=yi)。
可以按以下步骤进行线性扫描求解:
- 初始化答案变量 res=0,以及一个计数器 cnt=0,表示以当前位置作为结尾的连续互异区间的最大长度。
- 从左到右遍历下标 i(从 1 到 n):
- 若 xi=yi,则说明可以将当前元素接到之前的连续互异段后面,令 cnt=cnt+1。此时所有以 i 为右端点、长度不超过 cnt 的区间均为互异区间,数量恰好为 cnt 个,将 cnt 累加到 res 中。