Prüfe, ob die Summe der linken Seite des Arrays gleich der rechten Seite des Arrays in o (n) ist

Question

Ich wurde ein Array von Zahlen (Integer) gegeben und ich muss das Element zurückgeben, wenn die Summe der Zahlen auf seiner rechten Seite gleich ist die Summe der Zahlen in seiner linken Größe in o (n).

Zum Beispiel kann die Anordnung {1,2,2,9,3,2} sollte das Programm 9 drucken, da 1 + 2 + 2 = 5 und 3 + 2 = 5

ich meinen Code angehängt, aber es ist nicht o (n) Komplexität. schätze deine Hilfe.

Danke.

public class Program { 
    public static void checkIfEqualOption1(int[] arr){ 
     int sumRight = 0; 
     int sumLeft=0; 
     //sumRight+=numbers[0]; 
     for (int i=0; i < arr.length; i++){ 
      if (i>0){ 
       sumRight+=arr[i-1]; 
       for (int j=i+1; j<arr.length; j++){ 
        sumLeft+=arr[j]; 
       } 
       if (sumRight==sumLeft){ 
        System.out.println("\nFound = "+arr[i]); 
        break; 
       } 
      } 
     } 

    } 

    public static void print(int[] arr){ 
     for (int i=0; i < arr.length; i++){ 
      System.out.print(arr[i] + " "); 
     } 
    } 
    public static void main(String[] args) { 
     // TODO Auto-generated method stub 
     System.out.println("Hi"); 
     int[] numbers = {1,2,2,9,3,2}; 
     System.out.println("Array numbers:"); 
     for (int i=0; i < numbers.length; i++){ 
      System.out.print(numbers[i] + " "); 
     } 
     System.out.println("\n"); 
     checkIfEqualOption1(numbers); 
    } 
} 

Answer 1

beginnt mit der Beobachtung, dass für jeden i

arraySum(0, i) + arraySum(i+1, n) == arrayTotal 

so

arraySum(i+1, n) == arrayTotal - arraySum(0, i); 
^^^^^^^^^^^^^^^^     ^^^^^^^^^^^^^^^ 
Sum on the right     Sum on the left 

Berechne die arrayTotal im ersten Durchgang; Gehen Sie dann das Array von links und berechnen Sie die Partialsumme. Stoppen Sie, wenn Sie eine Position erreichen, wo

partialSum == arrayTotal - partialSum 

Answer 2

ich mit dieser Lösung kam, die beide Summen berechnet in Schritten von links und rechts Positionen (posFromLeft und posFromRight im Code unten), bis die Positionen haben „gekreuzt“ einander (posFromRight > posFromLeft ist nicht mehr erfüllt ist):

public class Program { 

public static void checkIfEqualOption1(int[] arr){ 
    int sumRight = 0; 
    int sumLeft=0; 
    int arrayLength=arr.length; 
    for (int posFromLeft=0; posFromLeft < arrayLength; posFromLeft++){ 
     int posFromRight=arrayLength-posFromLeft-1; 
     if (posFromRight > posFromLeft){ 

     sumRight+=arr[posFromRight]; 
     sumLeft+=arr[posFromLeft]; 
     } 
    } 
System.out.println("right sum: "+sumRight); 
System.out.println("left sum: "+sumLeft); 
} 


public static void main(String[] args) { 


    int[] numbers = {1,2,2,9,3}; 
    System.out.println("Array numbers:"); 
    for (int i=0; i < numbers.length; i++){ 
     System.out.print(numbers[i] + " "); 
    } 

    checkIfEqualOption1(numbers); 
} 
} 

Answer 3

Dies sollte in O(n) arbeiten, brauchen Sie nicht das Array zu sortieren:

public class Program { 

    public static void checkIfEqualOption1(int[] arr){ 

     int sumTotal=0; 
     for (int i=0; i < arr.length; i++){ // O(arr.length) 
      sumTotal += arr[i]; 
     } 

     int sumRight = 0; 
     int sumLeft=0; 
     for (int i=1; i < arr.length-1; i++){ // O(arr.length) 
      sumLeft += arr[i-1]; 
      sumRight = sumTotal - arr[i] - sumLeft; 
      if (sumRight == sumLeft){ 
       System.out.println("\nFound = "+arr[i]); 
       break; 
      } 
     } 
    } 


    public static void main(String[] args) { 

    int[] numbers = {1,2,2,9,3,2}; 
    System.out.println("Array numbers:"); 
    for (int i=0; i < numbers.length; i++){ 
      System.out.print(numbers[i] + " "); 
    } 
    System.out.println("\n"); 
    checkIfEqualOption1(numbers); 
    } 

} 

Diese Ausgänge:

Array numbers: 
1 2 2 9 3 2 


Found = 9 

Answer 4

Ich habe unten Code geschrieben, um die Gleichheit der Summe der LHS und RHS Array-Elemente zu überprüfen. getMidIndex() gibt den Array-Index zurück, wo er die Gleichheit gefunden hat.

public class Concepts { 

public static int getMidIndex(int[] elements) throws Exception { 
    int endIndex = elements.length - 1; 
    int startIndex = 0, sumL = 0, sumR = 0; 

    while (true) { 
     if (sumL > sumR) 
      sumR += elements[endIndex--]; 
     else 
      sumL += elements[startIndex++]; 
     System.out.println("StartIndex: " + startIndex + " Endindex: " + endIndex + " SumLeft: " + sumL 
       + " SumRight: " + sumR); 
     if (sumL == sumR) 
      break; 
     if (startIndex > endIndex) { 
      System.out.println("Invalid Array"); 
      break; 
     } 
    } 
    return endIndex; 
} 

public static void main(String[] args) throws Exception { 
    int[] array = { 1, 2, 2, 9, 3, 2 }; 
    int midVal = getMidIndex(array); 
    System.out.println("Mid index: " + midVal + " Value: " + array[midVal]); 
} 

}