具有最大值的连续子数组有多少个。 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

滑动 window 方法将适合作为此问题的更好解决方案，这将使我们能够在 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]}

Answer 2

我们可以在 O(n) 时间内解决这个问题，方法是保留两个指针 p_l 和 p_r，这两个指针都向上移动数组，同时更新频率计数 h[e]，对于我们遇到的每个元素以及当前唯一项的数量，k.

例如：

5 2
1 2 3 1 1

让我们看看每次迭代

k = 0
h = {}
total = 0
p_r = -1
p_l = -1

1:   p_r = 0
     h = {1:1}
     k = 1
     total = 1

2:   p_r = 1
     h = {1:1, 2:1}
     k = 2
     total = 1 + 2 = 3

3:   p_r = 2
     h = {1:1, 2:1, 3:1}
     k = 3

  => move p_l until k equals X:
     p_l = 0
     h = {1:1-1=0, 2:1, 3:1}
     k = 3 - 1 = 2

     total = 3 + 2 = 5

1:   p_r = 3
     h = {1:1, 2:1, 3:1}
     k = 3

  => move p_l until k equals X:
     p_l = 1
     h = {1:1, 2:1-1=0, 3:1}
     k = 3 - 1 = 2

     total = 5 + 2 = 7

1:   p_r = 4
     h = {1:2, 2:0, 3:1}
     k = 2
     total = 7 + 3 = 10

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

How many contiguous subarrays with max. n unique numbers

arrays

algorithm

sub-array