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

Question

我试图解决 this问题。

An integer M and a non-empty zero-indexed array A consisting of N non-negative integers are given. All integers in array A are less than or equal to M.

A pair of integers (P, Q), such that 0 ≤ P ≤ Q < N, is called a slice of array A. The slice consists of the elements A[P], A[P + 1], ..., A[Q]. A distinct slice is a slice consisting of only unique numbers. That is, no individual number occurs more than once in the slice.

For example, consider integer M = 6 and array A such that:

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

There are exactly nine distinct slices: (0, 0), (0, 1), (0, 2), (1, 1), (1,2), (2, 2), (3, 3), (3, 4) and (4, 4).

The goal is to calculate the number of distinct slices.

提前致谢。

#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，检查[A[fibot]]为真，因此，base = 2。但它应该是 1。所以你的代码返回 1 + 2 + 1 = 4 而正确答案 1 + 2 + 2 = 5。

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

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

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