arrays - 具有最大值的连续子数组有多少个。 n 个唯一编号

Question

我在网上发现了一个编程挑战，想知道是否有更有效的解决方案。

问题:给你一个包含 n 个数字的列表以及一个数字 X，它指的是可以包含在一个连续子数组中的不同数字的最大数量。我们需要对满足 X 施加的条件的所有此类连续子数组进行计数。

输入第一行是两个数字n和x；子数组中数字的数量和唯一数字的最大数量。

例子:

5 2
1 2 3 1 1
ans = 10
explanation: ([1],[2],[3],[1],[1],[1,2],[2,3],[3,1],[1,1],[3,1,1])

我的方法使用两个循环遍历列表的所有子数组，并计算相关子数组中唯一数字的数量(使用集合)。当然，必须有一种更有效的方法来计算这个？抱歉，如果这个问题不属于这里，请随时对其进行编辑。

编辑:nellex 的更正代码有时会给出错误答案

int main() {
    int n, x;
    cin >> n >> x;

    vector<int> a;
    for (int i = 1; i <= n; i++) {
        int b;
        cin >> b;
        a.push_back(b);
    }

    int ans = 0, end = 1;
    set<int> uniq;
    map<int, int> freq;
    for (int start = 0; start < n; start++) {
        cout << start << " and end=" << end << endl;
        while (uniq.size() <= x && end < n) {
            if (uniq.size() == x && freq[a[end]] == 0) {
                break;
            }
            uniq.insert(a[end]);
            freq[a[end]]++;
            end++;
        }
        cout << "added " << end << " - " << start << " to ans" << endl;
        ans += end - start;
        freq[a[start]]--;
        if (freq[a[start]] == 0) {
            uniq.erase(a[start]);
        }
    }
    cout << ans;
}

编辑:第一个测试用例约束:

1≤k≤n≤100

1≤xi≤10

最大的约束:

1≤k≤n≤5⋅10^5

1≤xi≤10^9

Answer 1

滑动窗口方法将适合作为此问题的更好解决方案，这将使我们能够通过使用 Set 和 Map 在 O(n*log(n)) 中解决它:https://ideone.com/v2CdZO

int main() {
    int n, x;
    cin >> n >> x;

    vector<int> a(n);
    for(int i = 0; i < n; i++) cin >> a[i];

    int end = 0;
    long long ans = 0;

    set<int> uniq;
    map<int, int> freq;
    for(int start = 0; start < n; start++) {
        while(uniq.size() <= x && end < n) {
            if(uniq.size() == x && freq[a[end]] == 0) {
                break;
            }
            uniq.insert(a[end]);
            freq[a[end]]++;
            end++;
        }
        ans += end - start;
        freq[a[start]]--;
        if(freq[a[start]] == 0) {
            uniq.erase(a[start]);
        }
    }
    cout << ans;
}

该算法的工作方式是，对于索引 start 定义的每个元素，即 a[start]，我们尝试找到最大的子数组开始在 start 这样子数组中的唯一元素是 <= x。如果识别出的子数组的大小是 S，那么我们知道元素 a[start] 将是从索引 start 开始的 S 个子数组的一部分。

如果我们对给定的示例进行试运行，

• 当 start = 1 时，我们将生成子数组 {[1], [1, 2]}
• 当 start = 2 时，我们将生成子数组 {[2], [2, 3]}
• 当 start = 3 时，我们将生成子数组 {[3], [3, 1], [3, 1, 1]}
• 当 start = 4 时，我们将生成子数组 {[1], [1, 1]}
• 当 start = 5 时，我们将生成子数组 {[1]}