You will be given an array A containing N integers. Find the longest sub-array which contains at most K distinct elements. Input First line contains two integers N, K (1 ≤ K ≤ N ≤ 5 × 105). Next line contains N integers Ai (0 ≤ Ai ≤ 106) - denoting the elements of the array. Output Print two integers L,R (1 ≤ L ≤ R ≤ N) - where L is the left index of the sub-array and R is the right index of the sub-array. If there are multiple sub-arrays with such property, you may print any of them. The elements of the array are numbered from 1 to n from left to right.C语言代码

以下是一种C语言的解法，该算法的时间复杂度为O(N)。

#include <stdio.h>
#include <stdlib.h>

#define MAX_N 500005

int n, k;
int a[MAX_N];
int cnt[MAX_N];

void solve() {
    int l = 1, r = 1, ans_l = 1, ans_r = 0, tot = 1;
    cnt[a[1]]++;
    while (r <= n) {
        while (tot <= k && r <= n) {
            r++;
            if (r <= n) {
                cnt[a[r]]++;
                if (cnt[a[r]] == 1) tot++;
            }
        }
        if (r - l > ans_r - ans_l) {
            ans_l = l;
            ans_r = r - 1;
        }
        while (tot > k) {
            cnt[a[l]]--;
            if (cnt[a[l]] == 0) tot--;
            l++;
        }
    }
    printf("%d %d\n", ans_l, ans_r);
}

int main() {
    scanf("%d%d", &n, &k);
    for (int i = 1; i <= n; i++) {
        scanf("%d", &a[i]);
    }
    solve();
    return 0;
}

该算法的思路是使用两个指针`l`和`r`来维护一个滑动窗口，该滑动窗口包含了最多`k`个不同的元素。具体来说，我们使用一个计数器数组`cnt`来记录滑动窗口中每个元素出现的次数，使用一个变量`tot`来记录滑动窗口中有多少个不同的元素。每次让`r`向右移动，如果此时滑动窗口中不同的元素个数不超过`k`，就更新答案。如果此时滑动窗口中不同的元素个数超过了`k`，就让`l`向右移动，直到滑动窗口中不同的元素个数不超过`k`为止。最后输出答案即可。