Какой самый эффективный способ найти общее количество различных подмассивов, имеющих различные элементы

Question

вот метод грубой силы, подсчитывающий различные наборы в наборе наборов. но это так неэффективно, что вряд ли можно назвать это решением, оцените вашу помощь. я уже пробовал хеширование, но не смог найти решение

int main(){
  int n;
  cin>>n;
  int v[n];
  set<int>s;
  set<set<int>>a;
  for(int h=0;h<n;h++)
  cin>>v[h];
  for(int h=0;h<n;h++){
    for(int j=h;j<n;j++){
    s.insert(v[j]);
    a.insert(s);
    }
    s.clear();
  }
cout<<a.size();
}

Answer 1

Общее количество подмассивов в массиве будет n*(n+1)/2. Потому что каждая позиция слева будет иметь подрешетку с n-позицией, и вы также реализовали то же самое в своем решении грубой силы.

Чтобы подсчитать весь массив с уникальными элементами, вы берете хэшированный набор и помещаете все числа это набор. Теперь, тогда, в этом случае, n будет размером хешированного набора.

Вы можете получить ответ в среднем за O(1) времени. Если вы используете упорядоченный набор деревьев, сложность времени будет O(logn).

. Я надеюсь, что смогу ответить на ваш вопрос. :)