计算不同切片的数量（仅包含唯一的数字）

Question

我解决了以下提供的协同问题。

给出了一个整数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 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).

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

编写函数：

类解决方案{公共int解决方案（int M，int[]A）；}

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

如果不同切片的数量大于1,000,000,000，则该函数应返回1,000,000,000。

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

A[0] = 3
A[1] = 4
A[2] = 5
A[3] = 5
A[4] = 2 the function should return 9, as explained above.

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

N是[1到100000]范围内的整数；M是[0..100000]范围内的整数；数组A的每个元素都是[0..M]范围内的整数。

我的解决方案在这里，

public static int solution(int M, int[] A) {

        boolean[] visited = new boolean[M + 1];

        int N = A.length;


        int result = 0;

        for (int i = 0; i < N; i++) {

            int k = i;
            int count = 0;

            while (i < N && !visited[A[i]]) {

                count++;
                visited[A[i]] = true;

                i++;
            }

            i -=1;

            // 3, 4, 5, 5, 2, 5, 4
            int j = i;

            while (j >= k && visited[A[j]]) {

                visited[A[j]] = false;
                j--;
            }

            result += count * (count + 1) / 2;
        }

        return result;
    }

然而，在线法官对正确性和性能的估计很低。如何改进？

Answer 1

我喜欢MBo阐明的双指针方法和对访问的数组进行O（1）更新的想法。这里有一个单指针的想法，它使用一个哈希集来实现唯一性，每次新段开始时，该哈希集都会被清除。

js lang-js prettyprint-override">function f(A){
  var sum = 0
  var set = new Set
  var len = 0
  
  for (a of A){
    if (sum >= 1000000000)
      return 1000000000
      
    if (set.has(a)){
      sum += len*(len+1)/2
      len = 1
      set.clear()
      
    } else {
      len++
      set.add(a)
    }
  }
  sum += len*(len+1)/2
  
  return Math.min(sum, 1000000000)
}

var A = [3, 4, 5, 5 ,2]

console.log(f(A))

Answer 2

似乎你选择了正确的方法，但在实现细节上犯了错误——在坏主意中降低索引。

制作两个索引-左索引和右索引。

a） 向右移动，直到满足重复元素（“stopper”）的要求-基本上，您是在第一个while循环中执行此步骤。如果你在停车前走了n步，则有n*（n-1）/2个切片。

b）现在向左移动索引，直到找到与“停止器”相同的元素并在它之后停止。当前切片再次良好

重复a）和b）直到结束。请注意，两个索引都只向前移动，复杂性是线性的