Subarreglos con elementos distintos

Dada una array, la tarea es calcular la suma de longitudes de subarreglos contiguos que tienen todos los elementos distintos.

Ejemplos: 

Input :  arr[] = {1, 2, 3}
Output : 10
{1, 2, 3} is a subarray of length 3 with 
distinct elements. Total length of length
three = 3.
{1, 2}, {2, 3} are 2 subarray of length 2 
with distinct elements. Total length of 
lengths two = 2 + 2 = 4
{1}, {2}, {3} are 3 subarrays of length 1
with distinct element. Total lengths of 
length one = 1 + 1 + 1 = 3
Sum of lengths = 3 + 4 + 3 = 10

Input :  arr[] = {1, 2, 1}
Output : 7

Input :  arr[] = {1, 2, 3, 4}
Output : 20

Una solución simple es considerar todos los subarreglos y, para cada subarreglo, verificar si tiene elementos distintos o si no usa hash . Y agregue longitudes de todos los subarreglos que tengan elementos distintos. Si usamos hashing para encontrar elementos distintos, entonces este enfoque toma tiempo O(n ² ) bajo el supuesto de que las operaciones de búsqueda e inserción de hash toman tiempo O(1).

Una solución eficiente se basa en el hecho de que si sabemos que todos los elementos en una array de subarreglo [i..j] son ​​distintos, la suma de todas las longitudes de los subarreglos de elementos distintos en esta array secundaria es ((j-i+1)*( j-i+2))/2. ¿Cómo? las posibles longitudes de los subarreglos son 1, 2, 3,……, j – i +1. Entonces, la suma será ((j – i +1)*(j – i +2))/2.

Primero encontramos el subarreglo más grande (con elementos distintos) a partir del primer elemento. Contamos la suma de longitudes en este subarreglo usando la fórmula anterior. Para encontrar el siguiente subarreglo del elemento distinto, incrementamos el punto inicial, i y el punto final, j a menos que (i+1, j) sean distintos. Si no es posible, incrementamos i nuevamente y avanzamos de la misma manera.

A continuación se muestra la implementación de este enfoque:

// C++ program to calculate sum of lengths of subarrays
// of distinct elements.
#include<bits/stdc++.h>
using namespace std;
 
// Returns sum of lengths of all subarrays with distinct
// elements.
int sumoflength(int arr[], int n)
{
    // For maintaining distinct elements.
    unordered_set<int> s;
 
    // Initialize ending point and result
    int j = 0, ans = 0;
 
    // Fix starting point
    for (int i=0; i<n; i++)
    {
        // Find ending point for current subarray with
        // distinct elements.
        while (j < n && s.find(arr[j]) == s.end())
        {
            s.insert(arr[j]);
            j++;
        }
 
        // Calculating and adding all possible length
        // subarrays in arr[i..j]
        ans += ((j - i) * (j - i + 1))/2;
 
        // Remove arr[i] as we pick new starting point
        // from next
        s.erase(arr[i]);
    }
 
    return ans;
}
 
// Driven Code
int main()
{
    int arr[] = {1, 2, 3, 4};
    int n = sizeof(arr)/sizeof(arr[0]);
    cout << sumoflength(arr, n) << endl;
    return 0;
}

// Java program to calculate sum of lengths of subarrays
// of distinct elements.
import java.util.*;
 
class geeks
{
 
    // Returns sum of lengths of all subarrays
    // with distinct elements.
    public static int sumoflength(int[] arr, int n)
    {
 
        // For maintaining distinct elements.
        Set<Integer> s = new HashSet<>();
 
        // Initialize ending point and result
        int j = 0, ans = 0;
 
        // Fix starting point
        for (int i = 0; i < n; i++)
        {
            while (j < n && !s.contains(arr[j]))
            {
                s.add(arr[j]);
                j++;
            }
 
            // Calculating and adding all possible length
            // subarrays in arr[i..j]
            ans += ((j - i) * (j - i + 1)) / 2;
 
            // Remove arr[i] as we pick new starting point
            // from next
            s.remove(arr[i]);
        }
 
        return ans;
    }
 
    // Driver Code
    public static void main(String[] args)
    {
        int[] arr = { 1, 2, 3, 4 };
        int n = arr.length;
 
        System.out.println(sumoflength(arr, n));
    }
}
 
// This code is contributed by
// sanjeev2552

# Python 3 program to calculate sum of
# lengths of subarrays of distinct elements.
 
# Returns sum of lengths of all subarrays
# with distinct elements.
def sumoflength(arr, n):
 
    # For maintaining distinct elements.
    s = []
 
    # Initialize ending point and result
    j = 0
    ans = 0
 
    # Fix starting point
    for i in range(n):
         
        # Find ending point for current
        # subarray with distinct elements.
        while (j < n and (arr[j] not in s)):
            s.append(arr[j])
            j += 1
 
        # Calculating and adding all possible
        # length subarrays in arr[i..j]
        ans += ((j - i) * (j - i + 1)) // 2
 
        # Remove arr[i] as we pick new
        # starting point from next
        s.remove(arr[i])
 
    return ans
 
# Driven Code
if __name__=="__main__":
     
    arr = [1, 2, 3, 4]
    n = len(arr)
    print(sumoflength(arr, n))
 
# This code is contributed by ita_c

// C# program to calculate sum of lengths of subarrays
// of distinct elements
using System;
using System.Collections.Generic;
     
public class geeks
{
 
    // Returns sum of lengths of all subarrays
    // with distinct elements.
    public static int sumoflength(int[] arr, int n)
    {
 
        // For maintaining distinct elements.
        HashSet<int> s = new HashSet<int>();
 
        // Initialize ending point and result
        int j = 0, ans = 0;
 
        // Fix starting point
        for (int i = 0; i < n; i++)
        {
            while (j < n && !s.Contains(arr[j]))
            {
                s.Add(arr[i]);
                j++;
            }
 
            // Calculating and adding all possible length
            // subarrays in arr[i..j]
            ans += ((j - i) * (j - i + 1)) / 2;
 
            // Remove arr[i] as we pick new starting point
            // from next
            s.Remove(arr[i]);
        }
 
        return ans;
    }
 
    // Driver Code
    public static void Main(String[] args)
    {
        int[] arr = { 1, 2, 3, 4 };
        int n = arr.Length;
 
        Console.WriteLine(sumoflength(arr, n));
    }
}
 
/* This code is contributed by PrinciRaj1992 */

<script>
 
// Javascript program to calculate sum of lengths of subarrays
// of distinct elements.    
 
    // Returns sum of lengths of all subarrays
    // with distinct elements.
    function sumoflength(arr,n)
    {
        // For maintaining distinct elements.
        let s=new Set();
        // Initialize ending point and result
        let j = 0, ans = 0;
   
        // Fix starting point
        for (let i = 0; i < n; i++)
        {
            while (j < n && !s.has(arr[j]))
            {
                s.add(arr[i]);
                j++;
            }
   
            // Calculating and adding all possible length
            // subarrays in arr[i..j]
            ans += Math.floor(((j - i) * (j - i + 1)) / 2);
   
            // Remove arr[i] as we pick new starting point
            // from next
            s.delete(arr[i]);
        }
   
        return ans;
    }
     
    // Driver Code
    let arr=[1, 2, 3, 4];
    let n = arr.length;
    document.write(sumoflength(arr, n));
     
    // This code is contributed by avanitrachhadiya2155
     
</script>

Producción: 

20

La complejidad temporal de esta solución es O(n). Tenga en cuenta que el ciclo interno se ejecuta n veces en total a medida que j va de 0 a n en todos los ciclos externos. Entonces hacemos operaciones O(2n) que es lo mismo que O(n).
Complejidad espacial: O(n), ya que se ha añadido n espacio extra

Este artículo es una contribución de Anuj Chauhan(anuj0503) . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.