Count individual slices in an array

Question

I tried to solve this problem .

An integer M and a non-empty null-indexed array A consisting of N are non-negative integers. 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. A slice consists of elements A [P], A [P + 1], ..., A [Q]. A different slice is a slice consisting only of unique numbers. That is, no individual number is found more than once in a slice.

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

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

There are exactly nine different sections: (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 individual slices.

Thanks in advance.

#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. R 0 n - 1 L , subarray ( , A[R] - , ).

: sum , int - 32- (, A ).

, , . ? base = fibot .

Answer 2

100% Ruby

LIMIT = 1_000_000_000

def solution(_m, a)
  a.each_with_index.inject([0, {}]) do |(result, slice), (back, i)|
    return LIMIT if result >= LIMIT
    slice[back] = true
    a[(i + slice.size)..-1].each do |front|
      break if slice[front]
      slice[front] = true
    end
    slice.delete back
    [result + slice.size, slice]
  end.first + a.size
end

Answer 3

Caterpillar , S(n+1) = S(n) + n + 1, S(n) - Java n -element , :

 public int solution(int top, int[] numbers) {
        int len = numbers.length;
        long count = 0;

        if (len == 1) return 1;

        int front = 0;
        int[] counter = new int[top + 1];

        for (int i = 0; i < len; i++) {
            while(front < len && counter[numbers[front]] == 0 ) {
                count += front - i + 1;
                counter[numbers[front++]] = 1;
            }

            while(front < len && numbers[i] != numbers[front] && i < front) {
                counter[numbers[i++]] = 0;
            }
            counter[numbers[i]] = 0;

            if (count > 1_000_000_000) {
                return 1_000_000_000;
            }
        }

        return (int)count;
    }