Codeforces Round #364 (Div. 2) C. They Are Everywhere __ two pointers or binary search

Source

Codeforces Round #364 (Div. 2)

My Solution

求包含所有种类的元素的最小区间长度

two pointers or binary search

1、binary search

int l = 0, r = n;

while(l + 1 < r){

x = (l + r) >> 1;

if(check(x)) r = x;         //O(n)的检查 sz = x 时是否满足条件， 如果满足则 r = x, 然后继续检查x更小的情况， 最后 ans == x;

else l = x;

}

复杂度 O(nlogn)

2、two pointers

用 sz 维护区间内的种类数 //如果每次用 .size()好像是 O(n) 的， 这样用个 sz 就变成 O(1)了

用m[flats[j]]、m[flats[i]] 表示 区间 [i, j) 内 各个元素的个数，

当 j 向右移一位 且原来的m[flats[j]] == 0 时 sz++, m[flats[j]]++;

当 i 向右移一位 且原来的m[flats[i]] == 1 时 sz--, m[flats[j]]--;

当sz == kinds 时， 维护答案 ans = min(ans, j - i);

复杂度 O(n)

Source code for two pointers

#include 
#include 
#include 

非特殊说明，本博所有文章均为博主原创，未经许可不得转载。

https://www.prolightsfxjh.com/

Thank you!

                                                                                                                                             ------from ProLightsfx