统计数组中的不同切片

Question

我试图解决this问题。

给出了一个整数M和一个非空的零索引数组A，其中包含N个非零的整数N 。在数组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,0.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开始。对于从0到n - 1的每个R到n - 1，请继续向右移动L，直到子数组仅包含不同的值（您可以保留数组中每个值的出现次数，并使用A[R]是可能出现的唯一元素比一次）。

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

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