Contiguos Subarray des gleichen Summenalgorithmus finden

Given array : 8 3 5 2 10 6 7 9 5 2
So the o/p will be Yes.

wie: {8,3,5} {10,6} {9,5,2} haben sie alle den gleichen Summenwert, d.h. 16.

But for this array : 1 4 9 6 2 12
o/p will be No.

as: Keine zusammenhängende Folie hat denselben Summenwert

Ich dachte daran zu gehen SubSetSum-Algorithmus / Kadane Maximaler SubArray-Algorithmus aber später komme ich zu Ende, da alle Algorithmen eine Zielsumme benötigen, die vordefiniert ist. Aber hier Wir kennen die Zielsumme nicht

Antworten:

1 für die Antwort № 1

Wenn die gewünschte Summe gegeben ist und alle Subarrays zusammenhängend sein sollten, dann ist es leicht möglich, dies zu tun O(n).

Führen Sie eine Schleife über das Array aus und behalten Sie die Grenzen der Slices bei (left und right Indizes) und currentSum.

Beginnen Sie mit dem ersten Element als 0. Die Grenzen sind [0, 0] (der Einfachheit halber schließen wir das Recht ein). Dann haben Sie in einer Schleife drei Bedingungen.

1. Wenn die Summe kleiner als gewünscht ist, fügen Sie das rechte Element zum Summen- und Vorwärtsrechtsindex hinzu
2. Wenn die Summe größer als gewünscht ist, entfernen Sie das linke Element aus dem Index für Summe und Fortschritt nach links
3. Wenn die Summe gleich ist, drucken Sie die Scheibe. Um dieses Segment in der nächsten Iteration zu vermeiden, bewegen Sie den linken Index nach vorne und passen Sie die Summe an.

Übersetzt nach Code

    public static void main(String[] args) {
int givenSum = 16;
int[] a = new int[] {8, 3, 5, 2, 10, 6, 7, 9, 5, 2};

// boundaries of slice
int left = 0; // defines position of slice
int right = 0; // exclusive
int currentSum = 0;

while (right < a.length) {

if (currentSum < givenSum) { // sum is not enough, add from the right
currentSum += a[right];
right++;
}

if (currentSum > givenSum) { // sum exceeds given, remove from the left
currentSum -= a[left];
left++;
}

if (currentSum == givenSum) { // boundaries of given sum found, print it
System.out.println(Arrays.toString(Arrays.copyOfRange(a, left, right)));
// remove the left element, so we can process next sums
currentSum -= a[left];
left++;
}
}

}

Für Ihren Fall druckt es 4 Scheiben, die Summe 16 ergeben

[8, 3, 5]
[10, 6]
[7, 9]
[9, 5, 2]

BEARBEITEN:

Wie OP klarstellte, ist keine gegebene Summe verfügbar, das Ziel ist zu prüfen, ob es mindestens zwei verschiedene zusammenhängende Subarrays gibt, die gleiche Summe ergeben.

Der einfachste Algorithmus besteht darin, alle möglichen Summen zu generieren und zu prüfen, ob Dubletten vorhanden sind

int[] a = new int[] {1, 4, 9, 6, 2, 12};

HashSet<Integer> sums = new HashSet<>();
int numOfSums = 0;

for (int left = 0; left < a.length - 1; left++) {
for (int right = left; right < a.length; right++) {
// sum from left to right
int sum = 0;
for (int k = left; k <= right; k++) {
sum += a[k];
}
numOfSums++;
sums.add(sum);
}
}
System.out.println(sums.size() == numOfSums);

Die Komplexität davon ist O(n^3)kein guter, aber funktioniert.

Tipp: Ein Trick könnte erforscht werden, um es zu verbessern O(n^2), Sie müssen nicht die Summe für jedes Scheibenpaar berechnen!

---

0 für die Antwort № 2

Sie können es auf folgende Weise tun

1. Sie haben die Gesamtsumme = 48
2. Jetzt hätte jede Teilmenge eine Summe, die einem Faktor von 48 entspricht. Je kleiner der Faktor, desto mehr Teilmengen können Sie einteilen
3. Überprüfen Sie für alle Faktoren der Summe, ob die Antwort für diesen Faktor möglich ist oder nicht. Dies kann in O (n) durchgeführt werden, indem einfach das Array durchlaufen wird.
4. Zeitkomplexität wäre O (n * Faktoren (Summe))

---

0 für die Antwort № 3

Verwenden Sie die dynamische Programmierung, um alle Subsummen des Arrays zu finden, und suchen Sie dann das Sub-Array mit derselben Summe. Die Komplexität sollte O (n2) sein.

    void subsum(int n, int* arr, int** sum) {
for (int i = 0; i < n; ++i) {
sum[i][i] = arr[i];
}
for (int l = 2; l <= n; ++l) {
for (int i = 0; i < n - l + 1; ++i) {
sum[i][i + l - 1] = sum[i][i + l - 2] + arr[i + l -1];
}
}
}

---