Méthode efficace pour résoudre la variation de la somme des sous-ensembles

Question

Étant donné un tableau de nombres entiers, trouvez le nombre maximum de sommes de adjacent éléments qui sont divisibles par n .

Exemple 1 :

input: long[] array = [1, 2, 3] , n = 7

output: 0

Exemple 2 :

input: long[] array = [1, 2, 4] , n = 7

output: 1

Exemple 3 :

input: long[] array = [2, 1, 2, 1, 1, 2, 1, 2] , n = 4

output: 6

Contraintes :

array.length = 50000

array[index] <= 2^31 - 1

n <= 2^31 - 1

Voici mon code actuel :

public static int maxSums(long[] array, long n) {

        int count = 0;

        if (array.length == 1 && array[0] == n) {
            return 1;

        } else {
            for (int i = 0; i < array.length; i++) {
                long sum = 0;
                for (int j = i; j < array.length; j++) {
                    sum += array[j];
                    if (sum % n == 0) {
                        count++;
                    }
                }
            }
        }
        return count;
    }

qui est essentiellement la technique de glissement de fenêtre. Cependant, ce code s'exécute avec une complexité temporelle O(n^2) ce qui est assez lent, et aboutit à Apex CPU Time Limit Exceeded vers l'extrémité supérieure des contraintes. Existe-t-il un moyen plus rapide de résoudre ce problème ?

Answer 1

Une approche à laquelle je viens de penser est O(n*m) , donde n est l'effectif n et m est la longueur du tableau.

L'algorithme se souvient, pour chaque sous-séquence jusqu'à l'indice courant, du rappel de la somme de la séquence. Cette information est stockée dans le tableau appelé currentMod .

Lors de l'itération sur le tableau d'entrée, ce currentMod est mis à jour. Nous ajoutons simplement à chaque valeur modulo possible de l'itération i-1 la valeur du tableau d'entrée à l'index i . Le tableau mis à jour comprend le nombre de sommes de sous-séquences se terminant à l'indice i pour chaque rappel possible : 0 , 1 , 2 jusqu'à n-1 .

Le premier élément de tmpMod à l'indice i comprend le nombre de sous-séquences qui se terminent à l'indice i et dont la somme est divisible par n . Par conséquent, nous les ajoutons à notre résultat final.

Voici l'algorithme :

public static int maxSums(int[] array, int n) {
    int[] currentMod = new int[n];
    int count = 0;

    for (int i = 0; i < array.length; i++) {
        // Add +1 to 0 remainder as a new sequence can start at every index which has sum 0
        currentMod[0] += 1;

        int[] tmpMod = new int[n];

        for (int j = 0; j < currentMod.length; j++) {
            // For every subsequence reminder of i-1 calculate the reminders of adding element i to every subsequence
            tmpMod[(j + array[i]) % n] += currentMod[j];
        }

        // Add number of subsequence sums that divide by n with remainder 0 to result 
        count += tmpMod[0];

        currentMod = tmpMod;
    }

    return count;
}

P.S. : Cet algorithme n'est pas strictement meilleur/mauvais que le vôtre. Il dépend d'une autre valeur d'entrée. Cela signifie qu'il dépend de vos entrées ce qui est plus efficace. Mon algorithme n'est meilleur que dans le cas de grands tableaux et d'un faible nombre de valeurs d'entrée. n valeurs.

EDIT : Après beaucoup de réflexion et de tests, je pense avoir trouvé une bonne solution. Il s'agit de O(n) en termes de complexité temporelle. Il est également O(n) en termes de complexité spatiale, car il peut y avoir au plus n des restes différents avec n dans le tableau.

L'algorithme garde la trace du reste actuel, qui est divisible par l'entrée. n depuis le début. Pour chaque nouvelle sous-séquence, nous ajoutons le 1 à l'état actuel des choses. De cette manière, nous définissons déjà quelle somme totale ( mod n ) nous avons besoin que la sous-séquence soit divisible par n .

public static int maxSums(int[] array, int n) {
    Map<Integer, Integer> currentMod = new HashMap<Integer, Integer>();
    int count = 0;
    int currentZero = 0;

    for (int val : array) {
        currentMod.put(currentZero, currentMod.getOrDefault(currentZero, 0) + 1);

        currentZero = (currentZero + val) % n;

        count += currentMod.getOrDefault(currentZero, 0);
    }

    return count;
}

Aussi, quelques comparaisons pour montrer que cela devrait fonctionner :

len(array)=50000 y n=1000 :

• Votre méthode : 11704 ms
• Mon ancien : 188 ms
• Mon nouveau : 13 ms

len(array)=50000 y n=1000000 :

• Votre méthode : 555 ms
• Mon ancien : s'est arrêté après 2 minutes
• Mon nouveau : 6 ms