如何解决CountDistinctSlices编码问题

Question

我正在尝试“CountDiinctSlices”代码性问题。我尽力了，得分30%，所以试图查找这样做的人以获得洞察力。基本上，我在答案中没有得到的是初始化的看到的数组（和M）的使用以及它是如何被使用的，得到它的人可以友好地引导我完成这段代码。

这是我没有解释就找到的答案

function solution(M, A) {
    // write your code in JavaScript (Node.js 8.9.4)
    let sum = 0;
    let front = 0;
    let back = 0;
    const seen = new Array(M+1).fill(false);
    while (front < A.length && back < A.length){
        while (front < A.length && seen[A[front]] !== true){
            sum += (front-back+1);
            seen[A[front]] = true;
            front += 1;
        }
        while (A[back] !== A[front]){
            seen[A[back]] = false;
            back += 1;
        }
        seen[A[back]] = false;
        back += 1;
    }           
    return Math.min(sum, 1000000000);
}

这是全部问题

给出了一个整数M和一个由N个非负整数组成的非空数组a。数组A中的所有整数都小于或等于M。

一对整数（P，Q），使得0≤ P≤ 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）。

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

编写函数：

function solution(M, A);

如果给定一个整数M和一个由N个整数组成的非空数组a，则返回不同的片数。

如果不同切片的数量大于1000000000，则函数应返回1000000000。

例如，给定整数M=6和数组A，以便：

A[0] = 3

A[1] = 4

A[2] = 5

A[3] = 5

A[4] = 2

如上所述，函数应返回9。

为以下假设编写一个有效的算法：

    N is an integer within the range [1..100,000];
    M is an integer within the range [0..100,000];
    each element of array A is an integer within the range [0..M].

Answer 1

我们先来看看算法：

>

首先从起点开始遍历，直到找到重复项。现在您有了一个范围=[后-前]

代码将此范围称为[back， Front]，其中“back”是开始，“Front”是您的移动指针。这个范围内有多少不同的切片？有大小为1、2、......的切片。前-后1，所以它是sum=1 2 3...[前-后1]

现在您遇到重复的应该怎么做？为了理解，让我们以问题中的示例为例：[3,4,5,5,2]。现在前到达5。现在我们应该将back指针带到5，但同时也要从集合中删除元素3,4,5，因为这些元素可能存在于当前前端之后。因此back来到5，当前由前指向。

让我们再举一个例子，因为这是找到的第一个重复项，所以前面的部分将到达索引处的1。现在应该回到哪里？它应该达到2，因为当您在向后移动指针的同时删除集合中的元素时，集合将不会有任何重复的位置。

执行此操作，直到前部到达阵列的末端。

关于您的问题，请参见：

如何在数组中找到重复项？可以使用集合，也可以使用布尔数组。我认为在这个问题中，M的唯一目的是指定数组中元素可以具有的最大值。因此，代码使用了一个大小为M的布尔数组。

如果使用布尔数组，一旦找到一个值元素，比如说v，就可以说v=true，这意味着它被“看到”。

或者，您可以使用一个集合并在需要时创建一个新的集合，而无需在每次发现重复的布尔数组时清除整个布尔数组，方法是让JavaScript处理垃圾收集，如下所示（未完全测试）：

function solution(M, A) {
    let sum = 0;
    let front = 0;
    let back = 0;
    let set = new Set();
    while (front < A.length) {
        while (front < A.length && !set.has(A[front])){
            sum += (front-back+1);
            set.add(A[front]);
            front += 1;
        }
        while (A[back] != A[front]) {
            set.delete(A[back]);
            back += 1;
        }
        set.delete(A[back]);
        back += 1;
    }           
    return Math.min(sum, 1000000000);
}