题目链接

https://codeforces.com/problemset/problem/616/D

解题思路

做过两遍了吧。
类似尺取法，不过尺子是不同数字的个数。
双指针。
右指针每到一个数字让cnt统计当前遍历到的区间中此数的个数++，左指针每到一个数字让cnt--。
若右指针向右移动时添加了区间内没有的数，则区间不同数字个数++，若左指针向右移动时删去了区间内唯一的一个此数值的数字，则区间不同数字个数--。
当l~r的区间内不同数字个数大于k时开始移动左指针，否则移动右指针，满足k时，更新最优解。

代码

#include<bits/stdc++.h>
using namespace std;

const int N = 1e6+10;

int n, k, a[N], dif, ans, cnt[N], bestr, bestl;

int main()
{
    scanf("%d%d", &n, &k);
    for(int i = 0;i < n;i ++) scanf("%d", &a[i]);
    for(int r = 0, l = 0;r < n;r ++) {
        if(cnt[a[r]] ++ <= 0) dif ++;
        while(dif > k && l <= r) {
            if(cnt[a[l++]] -- <= 1) dif --;
        }
        if(dif <= k) {
            if(ans < r-l+1) {
                bestr = r;
                bestl = l;
                ans = r-l+1;
            }
        }
    }
    printf("%d %d\n", bestl+1, bestr+1);
    return 0;
}