计算数组中的不同切片

Question

我试图解决这个问题.

给出了整数M和由N个非负整数组成的非空零索引数组A. 数组A中的所有整数都小于或等于M.

一对整数(P,Q),使得0≤P≤Q<N,称为阵列A的切片.切片由元素A [P],A [P + 1],...组成, A [Q].不同的切片是仅由唯一数字组成的切片.也就是说,切片中不会出现多个单独的数字.

例如,考虑整数M = 6和数组A,使得:

A[0] = 3
A[1] = 4
A[2] = 5
A[3] = 5
A[4] = 2 

有九个不同的切片:(0,0),(0,1),(0,2),(1,1),(1,2),(2,2),(3,3),( 3,4)和(4,4).

目标是计算不同切片的数量.

提前致谢.

#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);
}

Answer 1

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

首先，我给大家举一个反例。让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. 对于每个Rfrom0到n - 1，继续向右移动，L直到子数组仅包含不同的值（您可以维护数组中每个值的出现次数，并使用A[R]唯一可以出现多次的元素这一事实）。

您的代码还有一个问题：如果测试平台上的变量是 32 位类型（例如，如果 的所有元素都不同），则该sum变量可能会溢出。intA

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