c++ - 计算数组中的不同切片

我正在尝试解决this问题。



提前致谢。

#include <algorithm>
#include <cstring>
#include <cmath>
#define MAX 100002

// you can write to stdout for debugging purposes, e.g.
// cout << "this is a debug message" << endl;

using namespace std;

bool check[MAX];

int solution(int M, vector<int> &A) {
    memset(check, false, sizeof(check));
    int base = 0;
    int fibot = 0;
    int sum = 0;

    while(fibot < A.size()){

        if(check[A[fibot]]){
            base = fibot;
        }

        check[A[fibot]] = true;

   sum += fibot - base + 1;
        fibot += 1;
    }

    return min(sum, 1000000000);
}

最佳答案

解决方案不正确，因为您的算法错误。

首先，让我向您展示一个反例。让A = {2, 1, 2}。第一次迭代:base = 0，fibot = 0，sum += 1.正确。第二个:base = 0, fibot = 1，sum += 2。那也是对的。最后一步:fibot = 2，check[A[fibot]] is true，因此base = 2。但是应该是1。因此，您的代码返回1 + 2 + 1 = 4，而正确答案为1 + 2 + 2 = 5。

正确的方法可能是这样的:以L = 0开头。对于从R到0的每个n - 1，继续将L向右移动，直到子数组仅包含不同的值为止(您可以保持数组中每个值的出现次数，并使用A[R]是唯一可能出现更多的元素的事实不止一次)。

您的代码还有另一个问题:如果sum在测试平台上为32位类型(例如，如果int的所有元素都不同)，则A变量可能会溢出。

至于为什么您的算法不正确的问题，我不知道为什么它首先应该是正确的。你能证明这个吗？对我来说，base = fibot分配看起来很随意。